planor

Time limit: 0.5s Memory limit: 128MB Input: planor.in Output: planor.out

Un planor este lansat pe un teren format din NN parcele a câte un km, numerotate de la 1 la NN, dispuse liniar. Planorul este lansat de la începutul parcelei XX, de la înălțime zero. El planează peste cel mult KK parcele, KNK \leq 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țe

Date fiind numărul NN de parcele, KK - 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 NN 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ă XX de lansare și după ce parcurge exact K parcele;
  3. înălțimea maximă la care ajunge planorul, dacă alege convenabil o parcelă XX 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 CC, NN și KK, 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 NN numere, reprezentând, în ordinea de la 1 la NN, diferențele de nivel pentru cele NN 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 CC din fișierul de intrare.

Restricții și precizări

  • 1KN200 0001 \leq K \leq N \leq 200 \ 000;
  • 200 000-200 \ 000 \leq diferențele de nivel 200 000 \leq 200 \ 000;
  • Planorul poate ajunge la înălțime negativă în orice moment al zborului;
  • Pentru 1212 puncte, C=1C = 1;
  • Pentru 44 puncte, C=2C=2 și 1N5 0001 \leq N \leq 5 \ 000;
  • Pentru 1616 puncte, C=2C=2 și 10 000N200 00010 \ 000 \leq N \leq 200 \ 000;
  • Pentru 2020 de puncte, C=3C=3 și 1N5 0001 \leq N \leq 5 \ 000;
  • Pentru 4848 de puncte, C=3C=3 și 10 000N200 00010 \ 000 \leq N \leq 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 11 de la înălțime 00 și zburând o singură parcelă către dreapta, planorul va ajunge la înălțimea 44, 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 88 de la înălțime 00 și zburând patru parcele către dreapta, planorul va ajunge la înălțimea 1212. 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 99 de la înălțime 00 și zburând trei parcele către dreapta, planorul va ajunge la înălțimea 1313. Aceasta este înălțimea maximă posibilă.

Log in or sign up to be able to send submissions!