[USACO] 1-5-1 Number Triangles

/*
ID: 551100k1
LANG: C++
TASK: numtri
*/
#include<stdio.h>
#include<algorithm>
using namespace std;
int s[1005][1005],dp[1005][1005]={0};
int main(){
    freopen("numtri.in","r",stdin);
    freopen("numtri.out","w",stdout);
    int i,j,n;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        for(j=0;j<=i;j++)
            scanf("%d",&s[i][j]);
    for(i=0;i<n;i++)
        dp[n-1][i]=s[n-1][i];
    for(i=n-1;i>=0;i--)
        for(j=0;j<=i;j++)
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+s[i][j];
    printf("%d\n",dp[0][0]);
}