Ferma

ferma

==Include(page="template/taskheader" task_id="ferma")==

== include(page="template/taskheader" task_id="ferma") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| ferma.in | ferma.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="ferma") ==

==Include(page="template/raw")==
 
ferma
 
 
 
Zaharel s-a dus in vizita la bunicii lui de la tara impreuna cu Eugenia. Ferma bunicilor este de forma circulara, iar acolo cresc N gaini. Ferma a fost impartita in N sectoare, numerotate de la 1 la N, astfel incat oricare doua sectoare avand numere consecutive sunt adiacente (se afla unul langa altul). In plus, primul si ultimul sector sunt adiacente. In fiecare sector se afla cate o gaina, iar aceasta depune oua in fiecare zi. Bunicii stiu pentu fiecare gaina care este productivitatea ei, adica un numar care reprezinta diferenta dintre consumul gainii si cat produce. Zaharel si cu Eugenia strang de K ori pe zi oua de la gaini astfel: la fiecare strangere cei doi aleg o secventa (adica un sir de sectoare adiacente) formata din cel putin un sector, care contine numai gaini de la care nu s-au luat oua in acea zi.
 
h2. Cerinta
 
Cunoscand productivitatea fiecarea gaini cat si numarul de strangeri dintr-o zi, ajutati-i pe Zaharel si Eugenia sa stranga oua astfel incat suma productivitatilor gainilor de la care a strans oua sa fie maxima.
 
h2. Date de Intrare (fisier: ferma.in)
 
Pe prima linie se gasesc numerele naturale N si K. Pe urmatoarea linie se vor gasi N numere intregi reprezentand productivitatea fiecarei gaini.
 
h2. Date de Iesire (fisier: ferma.out)
 
Pe prima linie se va afisa suma maxima posibila a productivitatilor gainilor de la care se strang oua.
 
h2. Restrictii
 
S 2 <= N <= 10.000
 
S 1 <= K <= 1.000
 
S Productivitatea fiecarei gaini este un numar intreg din intervalul [-100.000, 100.000]
 
S Daca suma maxima posibila a productivitatilor este un numar negativ se va afisa 0 (se prefera sa nu se stranga nici un ou)
 
h2. Exemplu
 
ferma.in ferma.out
8 2 18
 
2 -6 4 3 -7 -9 10 -1
 
 
==Include(page="template/taskfooter" task_id="ferma")==