Fişierul intrare/ieşire:pagina.in, pagina.outSursăInfoarena Monthly 2012, Runda 12
AutorTeodor PlopAdăugată deTeodor94Teodor Plop Teodor94
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pagina

Printre noile obsesii ale lumii in care traim se numara si asezatul in pagina. Avem un text format din N cuvinte, in care cuvintele sunt despartite intre ele printr-un spatiu (" "), iar la finalul textului se afla caracterul punct ("."). Se considera ca latimea fiecarei litere din text este egala cu 1, iar latimea caracterelor punct (".") si spatiu (" ") este egala cu 0.

Dorim sa aflam latimea minima a unei pagini, astfel incat textul sa poata fi scris cursiv (fara cuvinte despartite in silabe). Mai precis, dorim ca fiecare rand sa se termine fie cu spatiul ce desparte doua cuvinte intre ele, fie cu punctul de la finalul textului.

Dandu-se N - numarul de cuvinte dintr-un text si L[i] - lungimea cuvintelor din text, in ordinea in care acestea apar, sa se spuna care este latimea minima a unei pagini pentru care textul poate sa fie scris cursiv.

Date de intrare

Fişierul de intrare pagina.in va contine pe prima linie numarul natural N, iar pe cea de-a doua linie cele N numere naturale L[i], reprezentand lungimile cuvintelor din text.

Date de ieşire

În fişierul de ieşire pagina.out se va afla un singur numar natural, reprezentand latimea minima a unei pagini ce respecta proprietatea ceruta.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ L[i] ≤ 109

Exemplu

pagina.inpagina.out
11
11 1 8 3 1 3 9 6 6 4 8
12

Explicatie

Randurile vor fi impartite in felul urmator:

Randul 1 va contine cuvintele 1 si 2
Randul 2 va contine cuvintele 3, 4, 5
Randul 3 va contine cuvintele 6 si 7
Randul 4 va contine cuvintele 8 si 9
Randul 5 va contine cuvintele 10 si 11

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?