1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 const int max_size=1001; 7 int n, a[max_size][max_size]; 8 int f[3][max_size]; 9 void initiate(){10     memset(a,-1,sizeof(a));11     memset(f,0,sizeof(f));12     for(int i=1;i<=n;i++){13         for(int j=1;j<=i;j++){14             scanf("%d",&a[i][j]);15         }16     }17 }18 void solve(){19     int pt_row=n;20     for(int column=1;column<=n;column++){21         f[pt_row%2][column]=a[pt_row][column];22     }23     for(int row=n-1;row>=1;row--){24         for(int pt_col=1;pt_col<=row;pt_col++){25             f[(pt_row-1)%2][pt_col]=a[pt_row-1][pt_col]+max(26                 f[pt_row%2][pt_col],27                 f[pt_row%2][pt_col+1]28             );29         }30         --pt_row;31     }32     printf("%d\n",f[pt_row%2][1]);33 }34 int main(){35     while(scanf("%d",&n)!=EOF){36         initiate();37         solve();38     }39     return 0;40 }