https://www.acwing.com/problem/content/900/

#include<bits/stdc++.h>
using namespace std;
int val[1000][1000];
int sum[1000][1000]={0};
int ans=-2e9;
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    for(int j=0;j<=i;j++)
    cin>>val[i][j];

  sum[0][0]=val[0][0];
     for(int i=1;i<n;i++)
    for(int j=0;j<=i;j++)
    {
        if(j==0)sum[i][0]=sum[i-1][0]+val[i][0];
        else if(j<i)sum[i][j]=max(sum[i-1][j]+val[i][j],sum[i-1][j-1]+val[i][j]);
        else if(j==i)sum[i][j]=sum[i-1][j-1]+val[i][j];
    }

    for(int j=0;j<=n-1;j++){

   ans=max(ans,sum[n-1][j]);

    }


cout<<ans;
    return 0;
}