WA on 29求条

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int kMaxN = 1e6 + 5;

int T, n, m;
vector<int> f[kMaxN], g[kMaxN], a[kMaxN];

struct Node {
  int mx = -1e18, mx2 = -1e18, p;
  void Init() { mx = mx2 = -1e18; }
  void Record(int x, int pos) {
    if (x >= mx) {
      mx2 = mx, mx = x, p = pos;
    } else if (x > mx2)
      mx2 = x;
  }
  int Q(int pos) {
    return (p != pos ? mx : mx2);
  }
} mx[2 * kMaxN];

signed main() {
  cin.tie(0)->ios::sync_with_stdio(0);
  for (cin >> T; T--;) {
    cin >> n >> m;
    for (int i = 0; i <= n + 1; i++) {
      f[i].resize(m + 2, -1e18);
      g[i].resize(m + 2, -1e18);
      a[i].resize(m + 2, 0);
    }
    for (int i = 1; i <= n + m; i++) mx[i].Init();
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        cin >> a[i][j];
        if (i == 1 && j == 1) {
          f[i][j] = a[i][j];
          continue;
        }
        f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j];
      }
    }
    for (int i = n; i; i--) {
      for (int j = m; j; j--) {
        if (i == n && j == m) {
          g[i][j] = a[i][j];
          continue;
        }
        g[i][j] = max(g[i + 1][j], g[i][j + 1]) + a[i][j];
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        mx[i + j].Record(f[i][j] + g[i][j] - a[i][j], i);
        // cout << f[i][j] << ' ';
      }
      // cout << '\n';
    }
    int mn = 1e18;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        // cout << mx[i + j].Q(i) << ' ';
        mn = min(mn, max(f[i][j] + g[i][j] - 3 * a[i][j], mx[i + j].Q(i)));
      }
      // cout << '\n';
    }
    cout << mn << '\n';
  }
}