Fişierul intrare/ieşire:teamwork.in, teamwork.outSursăAlgoritmiada 2016, Runda Finala, Juniori
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.7 secLimită de memorie128536 kbytes
Scorul tăuN/ADificultateN/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.inteamwork.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)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?