USACO-T018: Number Triangles

/*
ID: mickyta1
TASK: numtri
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;

const int N = 1000 + 5;

int arr[N][N], dp[2][N];

int main(){
    freopen("numtri.in", "r", stdin);
    freopen("numtri.out", "w", stdout);

    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= i; ++j){
            scanf("%d", &arr[i][j]);
        }
    }
    for(int i = n; i >= 1; --i){
        int cur = i % 2;
        int nxt = cur ^ 1;
        for(int j = 1; j <= n; ++j){
            dp[cur][j] = arr[i][j] + max(dp[nxt][j], dp[nxt][j + 1]);
        }
    }
    cout << dp[1][1] << '\n';

    fclose(stdin);
    fclose(stdout);
    return 0;
}