Fișierul intrare/ieșire | maxsum.in, maxsum.out | Sursă | Shumen juniori 2012 |
---|---|---|---|
Autor | Emil Kelevedjiev | Adăugată de | Marcela • Marcela |
Timp de execuție pe test | 3 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Maxsum (clasele 8-9)
Avem la dispoziție o secvență de n cutii. În fiecare cutie, există mai multe bile. Pe fiecare bilă este scris un număr întreg. Alegem 1, 2, ... sau toate cutiile și extragem cîte o bilă din fiecare dintre cutiile alese, păstrînd ordinea. Aliniem bilele în funcție de ordinea cutiilor. Secvența de numere rezultată trebuie sa fie nedescrescătoare.
Cerință
Scrie programul maxsum, care calculează suma maximă a acestor numere.
Date de intrare
Fișierul de intrare maxsum.in conține pe prima linie valoarea lui n. Pe următoarele linii găsim cîte bile sunt în fiecare cutie și numerele inscripționate pe acestea.
Date de ieșire
În fișierul de ieșire maxsum.out se tipărește suma maximă.
Restricții
- 0 ≤ n ≤ 500
- În fiecare cutie există cel puțin o bilă dar nu mai mult de 50
- Numărul înscris pe o bilă se află în intervalul de la 1 până la 1000.
Exemplu
maxsum.in | maxsum.out |
---|---|
10 3 2 2 4 2 1 2 3 3 7 10 4 5 5 1 1 1 3 1 2 3 1 9 1 1 5 7 8 1 1 1 1 2 1 1 3 |
25 |
Explicație
Secvența de bile extrase este 2 + 2 + 3 + 5 + 5 + 8. Din a 5-a, a 6-a, a 7-a și a 10-a cutie nu se extrage nicio bila.