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 nu este neapărat pozitivă. 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. În momentul în care Georgică deschide un seif, este obligat să ia toţi banii din acel seif.

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
  • Georgică poate pleca din bancă fără să deschidă vreun seif, în cazul în care această decizie este una înţeleaptă. În acest caz, profitul lui va fi egal cu 0.

Exemplu

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

Explicaţie

Georgică nu are voie să golească două seifuri aflate la distanţă strict mai mică decât 2. Altfel spus, Georgică nu are voie să golească două seifuri consecutive. Profitul maxim se obţine golind seiful 1 şi seiful 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content