1.5 Number Triangles

/*
id:y7276571
lang:c++
task:numtri
*/
/*
dp:f[i][j]=max{f[i+1][j], f[i+1][j+1]}(i >= 0 && j <= i)
*/
#include<iostream>
#include<cstdio>
#define max(x,y) x > y ? x : y
using namespace std;
const int maxn = 1000+1;
int main()
{
    freopen("numtri.in", "r", stdin);
    freopen("numtri.out", "w", stdout);
    int n, numtri[maxn][maxn];
    long maxsum = 0, f[maxn][maxn];
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j <= i; j++)
            cin >> numtri[i][j];
    for(int i = 0; i < n; i++)    f[n-1][i] = numtri[n-1][i];
    for(int i = n-2; i >= 0; i--)
        for(int j = 0; j <= i; j++)
        {
            f[i][j] = (max(f[i+1][j],f[i+1][j+1]))+numtri[i][j];
            if(maxsum < f[i][j])    maxsum = f[i][j];
//            cout << maxsum << endl;
        }
    cout << maxsum << endl;
/*
    for(int i = 0; i < n-1; i++)
    {
        for(int j = 0; j <= i; j++)
            cout << f[i][j] << " ";
        cout << endl;
    }
*/
    return 0;
}