# PBinfo #385 – SumTri – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

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 i al sumei se află pe linia i din 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

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
using namespace std;
#define NN 105
ifstream fin("sumtri.in");
ofstream fout("sumtri.out");
int n, a[NN][NN], S[NN][NN];
int main(){
	fin >> n;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=i;++j)
			assert(fin >> a[i][j]);
	S[1][1] = a[1][1];
	for(int i=2 ; i<=n ; ++i){
		S[i][1] = S[i-1][1]+a[i][1];
		S[i][i] = S[i-1][i-1]+ a[i][i];
		for(int j=2 ; j < i ; ++j)
			if(S[i-1][j-1]>S[i-1][j])
				S[i][j] = S[i-1][j-1] + a[i][j];
			else
				S[i][j] = S[i-1][j] + a[i][j];
	}
	int pmax = 1;
	for(int i = 2 ; i <= n ;++i)
		if(S[n][i]>S[n][pmax])
			pmax = i;
	fout << S[n][pmax];
	for(int i=1;i<=n;++i){
		for(int j=1;j<=i;++j)
			cout << S[i][j] << " ";
		cout << endl;
	}
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/385)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/385/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-385/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)