Code: The Turtle Strikes Back

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll infll = 1e18;
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }
    vector<vector<ll>> f(n, vector<ll>(m, -infll)), g(n, vector<ll>(m, -infll));
    f[0][0] = a[0][0], g[n - 1][m - 1] = a[n - 1][m - 1];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i)
                f[i][j] = max(f[i][j], f[i - 1][j] + a[i][j]);
            if (j)
                f[i][j] = max(f[i][j], f[i][j - 1] + a[i][j]);
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        for (int j = m - 1; j >= 0; --j) {
            if (i < n - 1)
                g[i][j] = max(g[i][j], g[i + 1][j] + a[i][j]);
            if (j < m - 1)
                g[i][j] = max(g[i][j], g[i][j + 1] + a[i][j]);
        }
    }
    vector<ll> mx1(n + m - 1, -infll), mx2(n + m - 1, -infll);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int d = i + j;
            ll val = f[i][j] + g[i][j] - a[i][j];
            if (val > mx1[d])
                mx2[d] = mx1[d], mx1[d] = val;
            else if (val > mx2[d])
                mx2[d] = val;
        }
    }
    ll res = infll;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int d = i + j;
            ll t1 = f[i][j] + g[i][j] - a[i][j], t2 = t1 - 2LL * a[i][j],
               t3 = (t1 == mx1[d] ? mx2 : mx1)[d];
            res = min(res, max(t2, t3));
        }
    }
    cout << res << '\n';
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _;
    cin >> _;
    while (_--)
        solve();
    return 0;
}