| Fişierul intrare/ieşire: | teamwork.in, teamwork.out | Sursă | Algoritmiada 2016, Runda Finala, Juniori |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 128536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Teamwork
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 Px (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(Px) * Suma(Px), pentru orice x membru al echipei (orice x, a ≤ x ≤ b).
Date de intrare
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.
Date de ieşire
Fişierul de ieşire teamwork.out va contine un singur numar natural reprezentand teamwork-ul maxim al unei echipe.
Restricţii
- 1 ≤ N ≤ 1.000.000
- -1.000.000 ≤ Px ≤ 1.000.000
Exemplu
| teamwork.in | teamwork.out |
|---|---|
| 12 7 -4 8 -5 -5 5 -5 -5 9 -3 1 1 | 88 |
| 8 7 -4 8 -20 9 -3 1 1 | 400 |
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)
