Primaria municipiului Bucuresti a hotarat sa scoata la licitatie cate un chiosc in fiecare dintre cele n statii de pe traseul autobuzului 2006. In acest scop Primaria a efectuat un studiu de fezabilitate cu ajutorul caruia a fost estimat profitul lunar, in RON, ce
poate fi obtinut de catre fiecare chiosc. In unele statii, aflate in zone mai putin circulate, s-a constatat ca este posibil sa nu se obtina nici un profit, ci chiar sa se inregistreze pierderi
(adica profitul sa fie negativ!). Pentru a putea sa vanda totusi toate chioscurile, Primaria a hotarat ca fiecare investitor interesat sa fie obligat sa cumpere chioscurile aflate in cel putin
k statii consecutive. Sarcina voastra este sa determinati secventa de chioscuri pentru care trebuie sa liciteze un investitor astfel incat profitul
estimat sa fie maxim. Deoarece orice investitor doreste sa pastreze relatii cordiale cu Primaria, in cazul in care nu exista nici o secventa de chioscuri care sa aduca profit el va licita pentru o
secventa de chioscuri pentru care pierderile sunt minime.
Cerinta
Fiind date numerele naturale n si k sa se determine profitul maxim ce poate fi obtinut pentru o secventa formata din cel putin k chioscuri dintre
cele n, precum si numerele de ordine ale primului, respectiv ultimului chiosc din secventa pentru care se obtine profit maxim. Chioscurile se
considera numerotate de la 1 la n.
Date de intrare
Fisierul de intrare ratb.in
contine pe prima linie numerele n si k,
despartite printr-un spatiu, iar pe a doua linie n
numere intregi, separate prin spatii, reprezentand in ordine profiturile estimate
pentru cele n chioscuri.
Date de iesire
Fisierul de iesire ratb.out
va contine pe prima linie profitul maxim cerut, iar pe a doua linie numerele
de ordine ale primului, respectiv ultimului chiosc din secventa pentru care
se obtine profitul maxim. Daca exista mai multe secvente pentru care profitul
este maxim se va considera aceea care se afla cat mai aproape de inceputul traseului
(chioscul de inceput sa fie minim; in cazul in care exista mai multe solutii
cu chioscul de inceput minim, se va alege solutia care are si chioscul de sfarsit
minim).
Restrictii
1<=k<=n<=5000
Profitul estimat pentru fiecare chiosc este un numar intreg nenul cuprins intre -1000 si 1000.
Exemple
ratb.in
ratb.out
ratb.in
ratb.out
10 3
23 -70 -73 82 -6 49 85 -118 37 26
210
4 7
7
2
-35 -12 -60 49 -80 -100 -20
-11
3 4
ratb.in
ratb.out
10
3
-100 10 10 10 -70 10 10 10 -50 -20
30
2 4
lect. drd. Radu Boriga
Universitatea "Titu Maiorescu" - Bucuresti Contact:r_boriga@yahoo.com