Fișierul intrare/ieșire	asasin.in, asasin.out	Sursă	ad-hoc
Autor	Mihai-Alexandru Dușmanu | Teodor Plop	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.05 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	0.75

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Assassin's Creed

Celebrul asasin Ezio Auditore a avut o peripetie putin comica – plecat in Venetia, furat de privelistile splendide ale orasului a uitat sa ii dea de mancare calului sau, Pol, asa ca acesta s-a suparat si l-a abandonat. Desigur, Ezio este mai presus de a parcurge drumul spre orasul sau natal, Florenta, pe jos, dar pentru a inchiria o trasura are nevoie de bani.

Norocul face ca tocmai atunci, cu ocazia carnavalului, un grup de templieri trecea prin oras. Cum asasinii sunt dusmanii de moarte ai templierilor, Ezio a decis ca va putea sa isi cumpere o trasura furand pungutele cu bani ale acestora.

Avantajul sau este ca acestia parcurg orasul intr-un sir indian, unul in spatele celuilalt.

In dezavantajul sau, insa, in grupul templierilor se afla si garzi de corp si cetateni obisnuiti. Ezio va aplica o tactica de jefuire atipica – isi va alege o tinta initiala, iar apoi va parcurge sirul de oameni, jefuindu-i succesiv. Asasinul hot poate abandona oricand sirul pentru a se reintoarce la o tinta aflata in fata ultimului om jefuit, dar aceasta manevra grabita il va costa toate castigurile pe care le obtinuse pana atunci; asa ca Ezio va trebui sa estimeze care este cea mai lunga insiruire de persoane care pot fi jefuite succesiv pentru un castig maxim. O alta problema o reprezinta garzile de corp, pe care Ezio trebuie sa le mituiasca din banii acumulati pentru a nu il aresta.

Dupa cum bine stiti, programarea nu era tocmai in voga in secolul XV, asa ca Ezio are nevoie de ajutorul vostru – daca va afla castigul maxim pe care il poate obtine, pozitia din sir a primei tinte cat si numarul de oameni jefuiti, eroul nostru va putea avea suficienti bani pentru a se intoarce in Florenta.

Se dau N, numarul de oameni care participa la carnaval, asezati in sir indian; si N numere intregi v[i], reprezentand suma de bani furata, respectiv pierduta de asasin in functie de tipul oamenilor din sir astfel:

• Daca v[i] ≤ 0, omul de pe pozitia i este gardian.
• Daca 0 ≤ v[i], omul de pe pozitia i este templier.
• Daca v[i] = 0, omul de pe pozitia i este un simplu cetatean.

Date de intrare

Fișierul de intrare asasin.in ...

Date de ieșire

În fișierul de ieșire asasin.out ...

Restricții

• 1 ≤ N ≤ 100000
• -1000 ≤ v[i] ≤ 1000, 1 ≤ i ≤ N

Exemplu

Explicație

...