8885번: Pirate Chest

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

시간복잡도는 $O(n^2m)$

#include<cstdio>
#include<algorithm>
using namespace std;
int a, b, n, m, d[501][501], sz[501];
pair<int, int> stk[501][501];
long long res;
void update(int x, int y, int h) {
    x = min(x, a);
    y = min(y, b);
    int s = x*y;
    res = max(res, s*(h + (1LL * h*s - 1) / (n*m - s)));
}
void push(int i, int x, int y, int h) {
    while (stk[i][sz[i]].first > h) {
        update(x, y - stk[i][sz[i] - 1].second - 1, stk[i][sz[i]].first);
        update(y - stk[i][sz[i] - 1].second - 1, x, stk[i][sz[i]].first);
        sz[i]--;
    }
    stk[i][++sz[i]] = { h,y };
}
int main() {
    scanf("%d%d%d%d", &a, &b, &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", d[i] + j);
            int x = 1e9;
            for (int k = i; k; k--) push(k, i - k + 1, j, x = min(x, d[k][j]));
        }
        for (int j = i; j; j--) push(j, i - j + 1, m + 1, 0), sz[j] = 0;
    }
    printf("%lld", res);
    return 0;
}