Easy Game

#include <bits/stdc++.h>
#define f(i,a,b) for(int i = (a); i <= (b); i++)

using namespace std;

const int INF = 1000000005;
int N, A[105], DP[105][105][2], S[105][105], T;

int dp(int l, int r, int turn)
{
    if(l+r==N) return 0;
    if(DP[l][r][turn] != INF) return DP[l][r][turn];
    int ret = turn ? INF : -INF;
    f(take,1,N-l-r)
    {
        // Take from the left

        if(turn) ret = min(ret, -S[l+1][l+take] + dp(l+take,r,1-turn));
        else ret = max(ret, S[l+1][l+take] + dp(l+take,r,1-turn));

        // Take from the right

        if(turn) ret = min(ret, -S[N-r-take+1][N-r] + dp(l,r+take,1-turn));
        else ret = max(ret, S[N-r-take+1][N-r] + dp(l,r+take,1-turn));
    }
    return DP[l][r][turn] = ret;
}

int main()
{
    cin >> T;
    f(tt,1,T)
    {
        cin >> N;
        f(i,1,N) cin >> A[i];
        f(l,0,N) f(r,0,N) S[l][r] = 0;
        f(l,1,N) f(r,l,N) S[l][r] = S[l][r-1] + A[r];
        f(l,0,N) f(r,0,N) f(t,0,1) DP[l][r][t] = INF;
        cout << "Case " << tt << ": " << dp(0,0,0) << "\n";
    }
}