Light OJ - 1071 / DP

/***
 created: 2022-08-29-21.55.04
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

ll a[102][102];
ll dp[102][102][102];
ll n,m;

ll solve(ll x,ll y,ll x1,ll y1)
{
    if(x==x1 && y==y1) return 0;

    if(x>n || y>m || x1>n || y1>m) return 0;

    if(dp[x][y][x1]!=-1) return dp[x][y][x1];

    ll val= a[x][y]+a[x1][y1];

    ll ans=max( { solve(x+1,y,x1+1,y1), solve(x+1,y,x1,y1+1), solve(x,y+1,x1,y1+1), solve(x,y+1,x1+1,y1) } );

    return dp[x][y][x1]=ans+val;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    test
    {
        ll i,j,k,ans;

        cin>>n>>m;

        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                cin>>a[i][j];
            }
        }

        memset(dp,-1,sizeof dp);

        ans= a[1][1] + a[n][m] + solve(1,2,2,1);

        cout<<"Case "<<cs<<": "<<ans<<nl;

    }

    get_lost_idiot;
}