renul despre
care discutam este format dintr-o locomotiva si N
vagoane (numerotate de la 1 la
N, incepand de la locomotiva).
In fiecare vagon se afla un numar cunoscut de pasageri (sa notam cu vi
numarul de pasageri din vagonul i).
Pasagerilor nu li se permite sa se deplaseze de la un vagon la altul.
Locomotiva s-a defectat si pentru a duce vagoanele la destinatie, pot fi utilizate
3 minilocomotive, aduse din statia de tren cea mai apropiata. O minilocomotiva
poate trage un numar mic de vagoane (maxim M),
iar in general cele 3 minilocomotive nu sunt suficiente pentru a trage toate vagoanele
din care este format trenul.
O minilocomotiva poate trage o secventa de vagoane (vagoane consecutive ale
trenului). Secventa de vagoane trasa de minilocomotiva 1 nu trebuie sa inceapa
neaparat cu primul vagon (minilocomotiva 1 poate trage mai intai pe o linie
moarta vagoanele de la inceputul trenului pe care nu le duce la destinatie si
apoi sa preia secventa de maxim M
vagoane pe care sa o duca la destinatie). Secventa de vagoane trasa de minilocomotiva
1 nu trebuie sa fie adiacenta cu secventa de vagoane trasa de minilocomotiva
2. Minilocomotiva 2 poate trage pe o linie moarta vagoanele situate intre ultimul
vagon tras de locomotiva 1 si primul vagon pe care locomotiva 2 intentioneaza
sa-l duca la destinatie.
In mod analog, secventa de vagoane trasa de minilocomotiva 2 nu trebuie sa fie
adiacenta cu secventa de vagoane trasa de minilocomotiva 3.
De exemplu, sa presupunem ca trenul are N=7
vagoane, iar o minilocomotiva poate trage maxim M=2
vagoane. Sa consideram ca numarul de pasageri din fiecare vagon este:
1
2
3
4
5
6
7
35
40
50
10
30
45
60
Daca minilocomotiva 1 duce la destinatie vagoanele 1-2, minilocomotiva 2 duce
vagoanele 3-4, iar minilocomotiva 3 duce vagoanele 6-7, numarul de pasageri care
ajung la destinatie este 240 si acesta este maximul posibil.
Cerinta
Scrieti
un program care sa determine numarul maxim de pasageri ce pot fi transportati
la destinatie cu cele 3 minilocomotive.
Date de intrare
Fisierul de intrare tren1.in contine
pe prima linie un numar natural N
reprezentand numarul de vagoane. Cea de a doua linie contine N
numere naturale separate prin cate un spatiu v1
v2 ... vN, reprezentand numarul de pasageri din fiecare vagon. Cea de
a treia linie contine un numar natural M
care reprezinta numarul maxim de vagoane care pot fi trase de o minilocomotiva.
Date de iesire
Fisierul
de iesire tren1.out contine o
singura linie pe care se afla numarul maxim de pasageri ce pot fi transportati
cu 3 minilocomotive.
Restrictii
M<=N<=50000
vi<=100, pentru orice 1<=i<=N
Exemplu
tren1.in
tren1.out
7
35 40 50 10 30 45 60
2
240
prof. Emanuela
Cerchez
Liceul de Informatica "Grigore Moisil" Iasi