(DP)Sums in a Triangle Problem Code: SUMTRIAN

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

#define endl         "\n"
#define ll           long long
#define PI           acos(-1.0)
#define GCD(a,b)     __gcd(a , b)
#define LCM(a,b)     ((a/__gcd(a,b))*b)
#define READ(f)      freopen(f,"r",stdin)
#define WRITE(f)     freopen(f,"w",stdout)
#define test         cout<<"\n*************\n"
#define mem(arr,val) memset(arr,val,sizeof(arr))
#define precise(c)   fixed(cout);cout<<setprecision(c)
#define valid(x,y)   (x>=1 && x<=row && y>=1 && y<=column)
#define fast         ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)



int main(){


    ll t;
    cin>>t;

    while(t--){

        ll r;
        cin>>r;

        ll arr[r+5][r+5];
        for(int i=1;i<=r;i++){
            for(int j=1;j<=i;j++){
                cin>>arr[i][j];
            }
        }

        for(int i=r;i>1;i--){
            for(int j=1;j<i;j++){

                arr[i-1][j] += max(arr[i][j],arr[i][j+1]);
            }
        }
        cout<<arr[1][1]<<endl;

    }

    return 0;
}