70蒟蒻求助
查看原帖
70蒟蒻求助
583610
DrAlfred楼主2023/8/9 11:19
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1010;
deque<int> que;
ll x[N][N], sum[N][N], s[N][N];
ll k[N][N], rk[N][N], ck[N][N];
ll n, m, a, b, c, d, ans = INT_MIN;
inline ll query(int x1, int y1, int i, int j) {
    int x2 = x1 + i - 1;
    int y2 = y1 + j - 1;
    return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}
inline void calcSum(int i, int j) {
    sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + x[i][j];
}
inline void initArea(void) {
    // puts("S:");
    for (int i = 1; i + a - 1 <= n; i++) {
        for (int j = 1; j + b - 1 <= m; j++) {
            s[i][j] = query(i, j, a, b);
            // printf("%d ", s[i][j]);
        }
        // putchar('\n');
    }
    // puts("K:");
    for (int i = 2; i + c - 1 < n; i++) {
        for (int j = 2; j + d - 1 < m; j++) {
            k[i - 1][j - 1] = query(i, j, c, d);
            // printf("%d ", k[i - 1][j - 1]);
        }
        // putchar('\n');
    }
    // a-c+1,b-d+1
    // puts("RK:");
    for (int i = 1; i + c + 1 <= n; i++) {
        que.clear();
        for (int j = 1; j + d + 1 <= m; j++) {
            if (!que.empty() && j - que.front() >= a - c + 1) {
                que.pop_front();
            }
            while (!que.empty() && k[i][que.back()] >= k[i][j]) {
                que.pop_back();
            }
            que.push_back(j);
            if (j >= a - c - 1) {
                rk[i][j - a + c + 2] = k[i][que.front()];
                // printf("rk: %d %d %d\n", i, j - a + c + 2, rk[i][j - a + c + 2]);
            }
        }
    }
    for (int j = 1; j + d + 1 - a + c + 2 <= m; j++) {
        que.clear();
        for (int i = 1; i + c + 1 <= n; i++) {
            if (!que.empty() && i - que.front() >= b - d + 1) {
                que.pop_front();
            }
            while (!que.empty() && rk[que.back()][j] >= rk[i][j]) {
                que.pop_back();
            }
            que.push_back(i);
            if (i >= b - d - 1) {
                ck[i - b + d + 2][j] = rk[que.front()][j];
            }
        }
    }
}
int main(int argc, char const *argv[]) {
    cin >> n >> m >> a >> b >> c >> d;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%lld", x[i] + j);
            calcSum(i, j);
        }
    }
    initArea();
    // 统计答案
    for (int i = 1; i + a - 1 <= n; i++) {
        for (int j = 1; j + b - 1 <= m; j++) {
            ans = max(ans, s[i][j] - ck[i][j]);
        }
    }
    printf("%lld\n", ans);
    return 0;
}

2023/8/9 11:19
加载中...