teamwork

Teamwork

== 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 copii 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~}$(*ATENTIE:* 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 naturale 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