Muresan Ciprian (mcip1977) Cerinţa
Se consideră un triunghi de numere întregi format dinn 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, în funcție de modul de parcurgere a numerelor din triunghi. Unul dintre aceste moduri este următorul:
- se pleacă din ultimul element al ultimei linii
- se merge întotdeauna spre stânga pe aceeași linie sau pe linia de deasupra, adică de pe linia
iși coloanajse merge pe liniaiși coloanaj-1sau pe liniai-1și coloanaj-1. - parcurgerile se termină pe prima coloană.
Să se determine cea mai mare sumă care se poate obține în acest mod.
Date de intrare
Fişierul de intrare sumtri_xi.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_xi.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 din intervalul
[-1000, 1000].
Exemplu:
sumtri_xi.in
5 4 1 4 2 -1 3 9 4 4 3 4 5 -2 2 1
sumtri_xi.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