== include(page="template/taskheader" task_id="teamwork") ==
Poveste şi cerinţă...
Compania Robin Hood, vestita pentru actele sale binefacatoare de a fura de la oameni saraci si a da la oameni bogati, vrea sa puna la cale un nou proiect care sa ajute copiii bogati din Marea Britanie. Pentru acest proiect voi trebuie sa selectati o echipa de oameni cat mai buna. Compania va pune la dispozitie o lista cu $N$ scla.. subalterni. Pentru fiecare subaltern $x$ se cunoaste productivitatea acestuia $P{~x~}$ (productivitatea poate sa fie si negativa daca acesta salveaza animalele de la disparitie, ajuta batranii nevoiasi sau chiar pastreaza ecologic mediul inconjurator).
Echipa trebuie formata dintr-un set de oameni aflati pe pozitii consecutive. Voi trebuie sa gasiti intervalul de oameni care produce un teamwork maxim. Teamwork-ul unei echipe se calculeaza in felul urmator: Productivitatea leader-ului * Suma productivitatii membrilor din echipa. Leader-ul este considerat a fi membrul cu productivitatea maxima. Mai exact, teamwork-ul unei echipe (sau a unui interval $[a,b]$) este $max(P{~x~}) * Suma(P{~x~})$, pentru orice $x$ membru al echipei $(orice x, a ≤ x ≤ b)$.
h2. Date de intrare
Fişierul de intrare $teamwork.in$ ...
Fişierul de intrare $teamwork.in$ va contine pe prima linie un numar natural $N$. Pe linia $2$ vor fi $N$ numere intregi reprezentand productivitatile angajatilor.
h2. Date de ieşire
În fişierul de ieşire $teamwork.out$ ...
Fişierul de ieşire $teamwork.out$ va contine un singur numar natural reprezentand teamwork-ul maxim al unei echipe.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1.000.000$
* $-1.000.000 ≤ P{~x~} ≤ 1.000.000$
h2. Exemplu
table(example). |_. teamwork.in |_. teamwork.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|12
7 -4 8 -5 -5 5 -5 -5 9 -3 1 1
|88|
|8
7 -4 8 -20 9 -3 1 1
|400
|
h3. Explicaţie
...
Pentru primul exemplu, costul secventei $[1,3]$ este $max(7, -4, 8) * (7 - 4 + 8) = 8 * 11 = 88$
Pentru cel de al doilea exemplu, costul secventei $[4,4]$ este $-20 * -20 = 400$ (un leader slab cu o echipa slaba pot fi foarte productivi)
== include(page="template/taskfooter" task_id="teamwork") ==
