80pts玄关求调

二维前缀和+单调队列
#include<cstdio>
#include<algorithm>
#include<deque>
using namespace std;
int n,m,a,b,c,d;
long long pre[1005][1005],s[1005][1005],out[1005][1005],inx[1005][1005],ans;
deque<int>ql[1005],qr;
int main(){
    scanf("%d %d %d %d %d %d",&n,&m,&a,&b,&c,&d);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        scanf("%lld",&s[i][j]);
        pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+s[i][j];
    }
    for(int i=a-1;i<=n;i++)for(int j=b-1;j<=m;j++)
        out[i][j]=pre[i+1][j+1]-pre[i-a+1][j+1]-pre[i+1][j-b+1]
                 +pre[i-a+1][j-b+1];
    // for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
    //     printf("OUT:%d %d %lld\n",i,j,out[i][j]);
    for(int i=c;i<=n;i++)for(int j=d;j<=m;j++)
        inx[i][j]=pre[i][j]-pre[i-c][j]-pre[i][j-d]+pre[i-c][j-d];
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++)
    //         printf("%3lld ",inx[i][j]);
    //     printf("\n");
    // }
    for(int i=c+1;i<n;i++){
        for(int j=d+1;j<m;j++){
            while(!ql[j].empty() && ql[j].front()<=i-a+c)
                ql[j].pop_front();
            while(!ql[j].empty() && inx[ql[j].back()][j]>=inx[i][j])
                ql[j].pop_back();
            ql[j].push_back(i);
            // printf("A:%d %d %lld\n",i,j,inx[ql[j].front()][j]);
        }
        qr.clear();
        for(int j=d+1;j<m;j++){
            while(!qr.empty() && qr.front()<=j-b+d)
                qr.pop_front();
            while(!qr.empty() && inx[ql[qr.back()].front()][qr.back()]
                               >=inx[ql[j].front()][j])
                qr.pop_back();
            qr.push_back(j);
            // printf("%d %d %lld\n",i,j,inx[ql[qr.front()].front()][qr.front()]);
            ans=max(ans,out[i][j]-inx[ql[qr.front()].front()][qr.front()]);
        }
    }
    printf("%lld",ans);
    return 0;
}