4011번: 기름 파기

https://www.acmicpc.net/problem/4011

$O(nm)$

격자를 한 구역당 하나의 k*k 정사각형이 들어가게끔 나눠보면 || 모양 혹은 T모양으로 나누는 경우밖에 없다.
따라서 적절히 prefix sum의 누적 최댓값들을 미리 구해놓고 격자를 나누는 모든 모양에 대해 원유 함유량의 최댓값을 구하면 된다.

한 가지 주의해야 할 점은,
1개의 사업자가 차지할 수 있는 최대 원유량은 3개의 사업자 것보다 클 수 없지만
2개의 사업자가 차지할 수 있는 양은 3개의 사업자 것보다 클 수 있기 때문에 이를 잘 고려해야 한다.
ex)

9 5 3
0 0 0 0 0
0 0 0 0 0
0 0 1 1 1
0 0 1 1 1
0 0 1 1 1
1 1 1 0 0
1 1 1 0 0
1 1 1 0 0
0 0 0 0 0

답은 18이 아닌 16이다.

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int m, n, k, s[1501][1501], lm[3][1501], a[1501][1501], res;
int block(int x1, int y1, int x2, int y2) {
    return s[x2][y2] - s[x2][y1] - s[x1][y2] + s[x1][y1];
}
void f() {
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    int um[1501][1502] = {}, dm[1502][1502] = {};
    for (int i = k; i <= m; i++) {
        for (int j = k; j <= n; j++) {
            um[i][n + 1 - j] = max({ um[i - 1][n + 1 - j],um[i][n + 2 - j],block(i - k,n - j,i,n + k - j) });
            dm[m + 1 - i][n + 1 - j] = max({ dm[m + 2 - i][n + 1 - j],dm[m + 1 - i][n + 2 - j],block(m - i,n - j,m + k - i,n + k - j) });
        }
    }
    for (int j = k; j <= n; j++) {
        int t = 0;
        for (int i = k; i <= m; i++) t = max({ t, block(i - k, j - k, i, j) });
        lm[0][j] = max(t, lm[0][j - 1]);
        for (int i = k; i <= m - k; i++) res = max(res, lm[0][j] + um[i][j + 1] + dm[i + 1][j + 1]);
        if (j >= k * 2) lm[1][j] = max(lm[1][j - 1], lm[0][j - k] + t);
        if (j >= k * 3) lm[2][j] = max(lm[2][j - 1], lm[1][j - k] + t);
    }
    res = max(res, lm[2][n]);
}
int main() {
    scanf("%d%d%d", &m, &n, &k);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) scanf("%d", a[i] + j);
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            f();
            for (int x = 1; x <= m; x++) reverse(a[x] + 1, a[x] + 1 + n);
        }
        for (int x = 1; x <= 1500; x++)
            for (int y = x; y <= 1500; y++) swap(a[x][y], a[y][x]);
        swap(m, n);
    }
    printf("%d", res);
    return 0;
}