| Fișierul intrare/ieșire | tren.in, tren.out | Sursă | .campion 2004 |
|---|---|---|---|
| Autor | Emanuela Cerchez | Adăugată de |
Cristian Frâncu
•
francu
|
| Timp de execuție pe test | 0.1 sec | Limită de memorie | 16384 KB |
| Scorul tău | N/A | Dificultate |
  4
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
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.in | tren.out |
|---|---|
| 7 35 40 50 10 30 45 60 2 |
240 |
