==Include(page="template/taskheader" task_id="secv2")==
==Include(page="template/badtests")==
Link: [1]File-List
Secventa 2
Gigel s-a decis sa devina olimpic la informatica, poate asa va reusi sa-si rezolve singur problemele, si nu va mai cere ajutorul vostru! La ora de informatica, profesoara lui i-a dat sa rezolve problema secventei de suma maxima: "Gigele, eu iti dau un sir N numere intregi, iar tu trebuie sa gasesti o secventa (adica un subsir de numere care apar pe pozitii consecutive in sirul initial) cu suma elementelor maxima!". Dupa vreo 30 de minute, Gigel s-a ridicat mandru si a zis: "Am gasit algoritmul de complexitate optima, doamna profesoara!"
Ca tema pentru acasa Gigel are de rezolvat aproape aceeasi problema: trebuie sa gaseasca secventa de suma maxima de lungime cel putin K!
Gigel s-a decis sa devina olimpic la informatica, poate asa va reusi sa-si rezolve singur problemele, si nu va mai cere ajutorul vostru! La ora de informatica, profesoara lui i-a dat sa rezolve problema secventei de suma maxima: "Gigele, eu iti dau un sir de $N$ numere intregi, iar tu trebuie sa gasesti o secventa (adica un subsir de numere care apar pe pozitii consecutive in sirul initial) cu suma elementelor maxima!". Dupa vreo 30 de minute, Gigel s-a ridicat mandru si a zis: "Am gasit algoritmul de complexitate optima, doamna profesoara!"
Ca tema pentru acasa Gigel are de rezolvat aproape aceeasi problema: trebuie sa gaseasca secventa de suma maxima de lungime cel putin $K$!
h2. Cerinta
Gigel inca nu stie destul de multa informatica ca sa poata rezolva aceasta problema, dar poate il ajutati voi! Scrieti un program care rezolva problema din tema lui Gigel.
h2. Date de Intrare
h2. Date de intrare
Fisierul de intrare secv2.in contine pe prima linie numerele N si K, separate prin spatiu. Pe cea de a doua linie se afla elementele sirului separate prin cate un spatiu.
Fisierul de intrare $secv2.in$ contine pe prima linie numerele $N$ si $K$, separate prin spatiu. Pe cea de a doua linie se afla elementele sirului separate prin cate un spatiu.
h2. Date de Iesire
h2. Date de iesire
Fisierul de iesire secv2.out trebuie sa contina o singura linie cu trei numere: pozitia de inceput si de sfarsit a secventei de suma maxima de lungime cel putin K si suma secventei.
Fisierul de iesire $secv2.out$ trebuie sa contina o singura linie cu trei numere: pozitia de inceput si de sfarsit a secventei de suma maxima de lungime cel putin $K$ si suma secventei.
h2. Restrictii si precizari
S 1 <= K <= N <= 50.000
S Elementele din vector sunt numere intregi din intervalul [-25.000, 25.000]
* $1 ≤ K ≤ N ≤ 50.000$
* Elementele din vector sunt numere intregi din intervalul $[-25.000, 25.000]$
h2. Exemplu
secv2.in secv2.out
8 3 3 7 9
0 -6 2 1 4 -1 3 -5
References
table(example). |_. secv2.in |_. secv2.out |
| 8 3
0 -6 2 1 4 -1 3 -5 | 3 7 9 |
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/secv2/enunt.files/filelist.xml
==Include(page="template/taskfooter" task_id="secv2")==
