Fişierul intrare/ieşire:tren.in, tren.outSursă.campion 2004
AutorEmanuela CerchezAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Tren (clasa a 8-a)

Trenul 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

Fişierul de intrare tren.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 ieşire

Fişierul de ieşire tren.out contine o singura linie pe care se afla numarul maxim de pasageri ce pot fi transportati cu 3 minilocomotive.

Restricţii

  • 1 ≤ M ≤ N ≤ 50000
  • vi ≤ 100, pentru orice 1 ≤ i ≤ N

Exemplu

tren.intren.out
7
35 40 50 10 30 45 60
2
240
Trebuie sa te autentifici pentru a trimite solutii. Click aici