Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-04-19 16:08:33.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:spargere2.in, spargere2.outSursăInfoarena Monthly 2014, Runda 4
AutorTeodor PlopAdăugată deTeodor94Teodor Plop Teodor94
Timp execuţie pe test0.2 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Spargere2

Georgică este un tip lacom. Jefuirea băncii Georgelonia este o nimica toată pe lângă noul gând măreţ al acestuia. De această dată, Georgică plănuieşte să jefuiască Petrilonia, marea rivală a băncii Georgelonia. Asemenea băncii Georgelonia, Petrilonia are N seifuri, numerotate de la 1 la N. În fiecare seif i se găseşte o sumă de bani v[i]. Pentru că Runda 4 şi pentru că Petrilonia, această sumă de bani poate fi şi negativă. Definim distanţa dintre două seifuri i şi j ca fiind |i - j|. Georgică ştie că dacă va deschide două seifuri care se află la distanţă strict mai mică decât K, se va declanşa alarma.

Cerinţă

Georgică se întreabă oare care este suma maximă de bani pe care o poate fura din banca Petrilonia, în timpul Rundei a 4-a, fără să declanşeze alarma.

Date de intrare

Fişierul de intrare spargere2.in conţine pe prima linie două numere naturale N şi K, având semnificaţia din enunt. Pe cea de-a doua linie, se vor găsi N numere naturale v[i].

Date de ieşire

În fişierul de ieşire spargere2.out se va găsi un singur număr natural, reprezentând răspunsul la întrebarea lui Georgică.

Restricţii

  • 1 ≤ K ≤ N ≤ 100.000
  • -109 ≤ v[i] ≤ 109

Exemplu

spargere2.inspargere2.out
4 2
1 -1 10 4
11

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?