Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | teamwork.in, teamwork.out | Sursă | Algoritmiada 2016, Runda Finala, Juniori |
Autor | Eugenie Daniel Posdarascu | Adăugată de | |
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 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 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 naturale 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 |
---|---|
8 7 -4 8 -20 9 -3 1 1 | 88 |
Costul secventei [1,3] este max(7, -4, 8) * (7 - 4 + 8) = 8 * 11 = 88
O alta secventa care producea un cost mare (dar nu cel mai bun) este secventa [5, 5] care producea 9 * 9 = 81