Monkey Banana Problem lightoj 1004

 In this problem we will check which adjacent cell will benefits the monkey best. For this, we will check all possible solution of this problem. For this course we will save previously solved subproblems and use it further.

codes:

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define ins insert
#define IOS ios::sync_with_stdio(false);
using namespace std;
int main()
{
    IOS
    int t;
    cin>>t;
    for(int no=1;no<=t;no++)
    {
        int n;
        cin>>n;
        ll arr[(2*n)-1][n];
        memset(arr,0,sizeof (arr[0][0])*((2*n)-1)*n);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                cin>>arr[i][j];
            }
        }
        for(int i=n;i<(2*n)-1;i++)
        {
            for(int j=0;j<((2*n)-1)-i;j++)
                cin>>arr[i][j];
        }
        for(int i=0;i<n;i++)
        {
            if(i==0) continue;
            for(int j=0;j<=i;j++)
            {
                ll x = 0, y = 0;
                if(j<i) x = arr[i-1][j];
                if(j>0) y = arr[i-1][j-1];
                arr[i][j] += max(x,y);
            }
        }
        for(int i=n;i<(2*n)-1;i++)
        {
            for(int j=0;j<((2*n)-1)-i;j++)
            {
                ll x = 0,y=0;
                x = arr[i-1][j];
                y = arr[i-1][j+1];
                arr[i][j] += max(x,y);
            }
        }
        cout <<"Case "<<no<<": " <<arr[(2*n)-2][0] <<endl;
    }
    return 0;
}