Fişierul intrare/ieşire: | colier2.in, colier2.out | Sursă | Vianuarena |
Autor | Din Folclor | Adăugată de | |
Timp execuţie pe test | 0.5 sec | Limită de memorie | 1024 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Colier 2 (clasa a 9-a)
Notă: această problemă este o modificare a problemei colier. Are acelaşi enunţ, dar limita de memorie a fost micşorată.
De ziua îndrăgostiţilor Macarie s-a gândit să-i cumpere Petronelei un colier. Cum însă nu are foarte mulţi bani, a apelat la un magazin online ieftin (şi bun). Din păcate colierul primit, format din N pietre preţioase are şi defecte. Pentru fiecare piatră preţioasă se cunoaşte nivelul de frumuseţe (care poate fi un număr negativ în cazul defectelor). Macarie vrea să păstreze doar o parte din pietrele preţioase, astfel încât să obţină un colier cât mai frumos. Pietrele păstrate trebuie să fi fost pe poziţii consecutive în colierul iniţial. Colierul este circular, ceea ce înseamnă că după ultima piatră urmează prima. Frumuseţea colierului rezultat este suma frumuseţilor pietrelor selectate.
Macarie nu se pricepe foarte bine la calcule şi vă cere ajutorul. Ar vrea să ştie nivelul maxim de frumuseţe pe care-l poate obţine din colierul dat prin extragerea unui număr de pietre aflate pe poziţii consecutive.
Date de intrare
Fişierul de intrare colier2.in conţine pe prima linie N = numărul de pietre din colierul dat, iar pe următoarele N linii câte un număr întreg reprezentând nivelul de frumuseţe al fiecărei pietre preţioase.
Date de ieşire
În fişierul de ieşire colier2.out se va scrie valoarea maximă care poate fi obţinută prin extragerea unui număr de pietre aflate pe poziţii consecutive.
Restricţii
- 1 ≤ N ≤ 1000000
- -1000 ≤ nivelul de frumuseţe al fiecărei pietre pretioase ≤ 1000
- Colierul este un şir circular. Pot fi alese un număr de pietre aflate la începutul şirului afişat împreună cu un număr de pietre aflate la sfârşit
- Macarie trebuie să selecteze cel puţin o piatră pretioasă (colierul format va avea cel puţin o piatră)
Exemplu
colier.in | colier.out | Expplicaţie |
---|---|---|
7 -2 1 2 -1 0 1 -2 | 3 | Nivelul maxim de frumuseţe care se poate obţine este 3, selectând pietrele de la poziţia 2 la poziţia 3 sau pietrele de la 2 la poziţia 6. |
6 1 0 -5 2 -8 1 | 2 | Nivelul maxim de frumuseţe care se poate obţine este 2, selectând prima şi ultima piatră, sau selectând primele două şi ultima piatră, sau alegând doar piatra cu valoarea 2, aflată pe poziţia 4. |