Submission #617990

---

Source Code Expand

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
#include<complex>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

const int MAX = 333;
const ll INF = 1ll<<55;
ll B[MAX][MAX];
ll total[MAX][MAX];
ll memoy[MAX][MAX];
ll memox[MAX][MAX];
ll dpy[MAX][MAX];
ll dpx[MAX][MAX];

ll getSum(int y1, int x1, int y2, int x2) {
    return total[y2][x2] - total[y2][x1-1] - total[y1-1][x2] + total[y1-1][x1-1];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W;
    cin >> H >> W;
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
        cin >> B[i][j];
    }
    for (int i = 1; i <= H; i++) for (int j = 1; j <= W; j++) {
        total[i][j] = total[i-1][j] + total[i][j-1] - total[i-1][j-1] + B[i-1][j-1];
    }
    // memo
    for (int y1 = 1; y1 <= H; y1++) for (int y2 = y1; y2 <= H; y2++) {
        memoy[y1][y2] = -INF;
        vector<ll> memo(W+1);
        for (int i = 1; i <= W; i++) memo[i] = min(memo[i-1], getSum(y1, 1, y2, i));
        for (int r = 1; r <= W; r++) memoy[y1][y2] = max(memoy[y1][y2], getSum(y1, 1, y2, r) - memo[r-1]);
        //for (int x1 = 1; x1 <= W; x1++) for (int x2 = x1; x2 <= W; x2++) {
        //    memoy[y1][y2] = max(memoy[y1][y2], getSum(y1, x1, y2, x2));
        //}
    }
    for (int x1 = 1; x1 <= W; x1++) for (int x2 = x1; x2 <= W; x2++) {
        memox[x1][x2] = -INF;
        vector<ll> memo(H+1);
        for (int i = 1; i <= H; i++) memo[i] = min(memo[i-1], getSum(1, x1, i, x2));
        for (int r = 1; r <= H; r++) memox[x1][x2] = max(memox[x1][x2], getSum(1, x1, r, x2) - memo[r-1]);
        //for (int y1 = 1; y1 <= H; y1++) for (int y2 = y1; y2 <= H; y2++) {
        //    memox[x1][x2] = max(memox[x1][x2], getSum(y1, x1, y2, x2));
        //}
    }
    // dp
    for (int x1 = 1; x1 <= W; x1++) for (int x3 = x1+1; x3 <= W+1; x3++) {
        dpx[x1][x3] = -INF;
        for (int x2 = x1; x2 < x3; x2++) dpx[x1][x3] = max(dpx[x1][x3], memox[x1][x2]);
    }
    for (int y1 = 1; y1 <= H; y1++) for (int y3 = y1+1; y3 <= H+1; y3++) {
        dpy[y1][y3] = -INF;
        for (int y2 = y1; y2 < y3; y2++) dpy[y1][y3] = max(dpy[y1][y3], memoy[y1][y2]);
    }
    // solve
    ll ans = -INF;
    for (int x1 = 1; x1 <= W; x1++) for (int x3 = x1+1; x3 <= W; x3++) {
        ans = max(ans, dpx[x1][x3] + dpx[x3][W+1]);
    }
    for (int y1 = 1; y1 <= H; y1++) for (int y3 = y1+1; y3 <= H; y3++) {
        ans = max(ans, dpy[y1][y3] + dpy[y3][H+1]);
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result