Atenție! Aceasta este o versiune veche a paginii., scrisă la 2013-02-16 11:39:59.
Revizia anterioară   Revizia următoare  

Fișierul intrare/ieșire colier.in, colier.out Sursă Vianuarena
Autor din folclor Adăugată de avatar vmanz Victor Manz vmanz
Timp de execuție pe test 0.5 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Colier (clasa a 9-a)

De ziua indragostitilor Macarie s-a gandit sa-i cumpere Petronelei un colier. Cum insa nu are foarte multi bani, a apelat la un magazin online ieftin (si bun). Din pacate colierul primit, format din N pietre pretioase are si defecte. Pentru fiecare piatra pretioasa se cunoaste nivelul de frumusete (care poate fi un numar negativ in cazul defectelor). Macarie vrea sa pastreze doar o parte din pietrele pretioase, astfel incat sa obtina un colier cat mai frumos. Pietrele pastrate trebuie sa fi fost pe pozitii consecutive in colierul initial. Macarie nu se pricepe foarte bine la calcule si va cere ajutorul. Ar vrea sa stie nivelul maxim de frumusete pe care-l poate obtine din colierul dat prin extragerea unui numar de pietre aflate pe pozitii consecutive si in cate moduri se poate face alegerea.

Date de intrare

Fișierul de intrare colier.in contine pe prima linie N = numarul de pietre din colierul dat, iar pe urmatoarele N linii cate un numar intreg reprezentand nivelul de frumusete al fiecarei pietre pretioase.

Date de ieșire

În fișierul de ieșire colier.out vor fi scrise, pe prima linie valoarea maxima care poate fi obtinuta prin extragerea unui numar de pietre aflate pe pozitii consecutive, iar pe a doua linie numarul de variante de obtinere a acesteia.

Restricții

  • 1 ≤ N ≤ 1000000
  • -1000 ≤ nivelul de frumusete al fiecarei pietre pretioase ≤ 1000
  • Colierul este un sir circular. Pot fi alese un numar de pietre aflate la inceputul sirului afisat impreuna cu un numar de pietre aflate la sfarsit
    1 &Macarie trebuie sa selecteze cel putin o piatra pretioasa

Exemplu

colier.in colier.out
6 1 0 -5 2 -8 1
2 3

Explicație

Nivelul maxim de frumusete care se poate obtine este 2. Exista trei variante de obtinere a acestuia: Selectand prima si ultima piatra, sau selectand primele doua si ultima piatra, sau alegand doar piatra cu valoarea 2, aflata pe pozitia 4.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii