Pracsiu Dan (dnprx) Un planor este lansat pe un teren format din N parcele a câte un km, numerotate de la 1 la N, dispuse liniar. Planorul este lansat de la începutul parcelei X, de la înălțime zero. El planează peste cel mult K parcele, K ≤ N, în sensul crescător al numărului de parcelă, iar apoi se oprește.
Fiecare parcelă dispune de curenți verticali, care fie înalță, fie coboară planorul. Pentru fiecare parcelă se cunosc numărul de metri cu care planorul își modifică înălțimea pe parcursul traversării acelei parcele (să numim acest număr diferență de nivel). Acest număr poate fi pozitiv, dacă el câștigă în înălțime, sau negativ, dacă pierde în înălțime.
Cerința
Date fiind numărul N de parcele, K – numărul maxim de parcele pe care le poate parcurge planorul ce pornește de la înălțime zero, precum și diferențele de nivel corespunzătoare fiecăreia dintre cele N parcele să se rezolve următoarele 3 cerințe:
1) înălțimea maximă la care ajunge planorul dacă pleacă din prima parcelă și parcurge cel mult K parcele (dar cel puțin una);
2) înălțimea maximă la care ajunge planorul, dacă alege convenabil o parcelă X de lansare și după ce parcurge exact K parcele;
3) înălțimea maximă la care ajunge planorul, dacă alege convenabil o parcelă X de lansare și parcurge cel mult K parcele (dar cel puțin una).
Date de intrare
Fișierul de intrare planor.in conține pe prima linie numerele C, N și K, reprezentând numărul cerinței (1, 2 sau 3), numărul de parcele și respectiv numărul maxim de parcele parcurse. A doua linie conține N numere, reprezentând, în ordinea de la 1 la N, diferențele de nivel pentru cele N parcele. NUmerele scrise pe aceeași linie sunt separate prin câte un spațiu.
Date de ieșire
Fișierul de ieșire planor.out va conține o singură linie pe care va fi scris un singur număr, răspunsul la cerința C din fișierul de intrare.
Restricții și precizări
1 ≤ K ≤ N ≤ 200.000−200.000 ≤ diferențele de nivel ≤ 200.000- Planorul poate ajunge la înălțime negativă în orice moment al zborului.
- Pentru 12 puncte,
C = 1 - Pentru 4 puncte,
C = 2și1 ≤ N ≤ 5.000 - Pentru 16 puncte,
C = 2și10.000 ≤ N ≤ 200.000 - Pentru 20 puncte,
C = 3și1 ≤ N ≤ 5.000 - Pentru 48 puncte,
C = 3și10.000 ≤ N ≤ 200.000
Exemplul 1:
planor.in
1 14 4 4 -5 3 -2 6 3 -2 -1 4 3 6 -4 2 3
planor.out
4
Explicație
Plecând de la parcela 1 de la înălțime 0 și zburând o singură parcelă către dreapta, planorul va ajunge la înălțimea 4, care este maximă posibil.
Exemplul 2:
planor.in
2 14 4 4 -5 3 -2 6 3 -2 -1 4 3 6 -4 2 3
planor.out
12
Explicație
Plecând de la parcela 8 de la înălțime 0 și zburând patru parcele către dreapta, planorul va ajunge la înălțimea 12. Aceasta este înălțimea maximă posibilă.
Exemplul 3:
planor.in
3 14 4 4 -5 3 -2 6 3 -2 -1 4 3 6 -4 2 3
planor.out
13
Explicație
Plecând de la parcela 9 de la înălțime 0 și zburând trei parcele către dreapta, planorul va ajunge la înălțimea 13. Aceasta este înălțimea maximă posibilă.