Candale Silviu (silviu) Cerinţa
Se consideră un triunghi de numere naturale format din n linii.Prima linie conține un număr, a doua linie conține 2 numere, etc. ultima linie n, conține n numere. În acest triunghi se pot calcula diverse sume cu n elemente, astfel:
- termenul
ial sumei se află pe liniaidin triunghi - pentru un anumit termen al sumei, termenul următor se află pe linia următoare și pe aceeași coloană, sau pe coloana imediat următoare spre dreapta.
Să se determine cea mai mare sumă care se poate obține în acest mod.
Date de intrare
Fişierul de intrare sumtri.in conţine pe prima linie numărul n. Fiecare dintre următoarele n linii conține câte o linie a triunghiului.
Date de ieşire
Fişierul de ieşire sumtri.out va conţine pe prima linie numărul S, reprezentând cea mai mare sumă care se poate obține.
Restricţii şi precizări
1 ≤ n ≤ 100- numerele din triunghi sunt mai mici decât
1000
Exemplu:
sumtri.in
5 4 1 4 2 1 3 9 4 4 3 4 5 2 2 1
sumtri.out
21
Explicație
Suma 21 se poate obține adunând numerele:
| 4 | ||||
| 1 | 4 | |||
| 2 | 1 | 3 | ||
| 9 | 4 | 4 | 3 | |
| 4 | 5 | 2 | 2 | 1 |