F - Monkey Banana Problem (24-11)

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

const int N = 10005;

ll a[205][105];
ll dp[205][105];

ll solve(ll n, ll k) {

    memset(dp, 0, sizeof(dp));

    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= i; ++j)
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j];

    for(int i = n + 1; i <= k; ++i)
        for(int j = 1; j <= n; ++j)
            dp[i][j] = max(dp[i-1][j+1], dp[i-1][j]) + a[i][j];

    return dp[k][1];
}

int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("F-MonkeyBananaProblem.inp", "r", stdin);
    //freopen("F-MonkeyBananaProblem.out", "w", stdout);
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL); cout.tie(NULL);

    int t; cin >> t;
    for(int test = 1; test <= t; ++test){
        ll n; cin >> n;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= i; ++j)
                cin >> a[i][j];

        ll k = 2*n - 1;
        ll m = n;
        for(int i = n + 1; i <= k; ++i) {
            m--;
            for(int j = 1; j <= m; ++j)
                cin >> a[i][j];
        }
        cout << "Case " << test << ": " << solve(n, k) << endl;
    }
    return 0;
}