题目描述
为了增添公园的景致，现在需要在公园中修筑一个花坛，同时在画坛四周修建一片绿化带，让花坛被绿化带围起来。
如果把公园看成一个M*N的矩形，那么花坛可以看成一个C*D的矩形，绿化带和花坛一起可以看成一个A*B的矩形。
如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度之和，那么，
绿化带的肥沃度=A*B块的肥沃度-C*D块的肥沃度
为了使得绿化带的生长得旺盛，我们希望绿化带的肥沃度最大。
输入输出格式
输入格式：第一行有6个正整数M,N,A,B,C,D
接下来一个M*N的数字矩阵，其中矩阵的第i行j列元素为一个整数Xij,表示该花园的第i行第j列的土地“肥沃度”。
输出格式：一个正整数，表示绿化带的最大肥沃程度。
输入输出样例
说明
数据范围
30%的数据，1<=M,N<=50
100%的数据，1<=M,N<=1000,1<=A<=M,1<=B<=N,1<=C<=A-2,1<=D<=B-2，1<=“肥沃度”<=100
/*和理想的正方形这道题比较类似
首先我们把所有a*b块的和用mx数组记录下来，这里需要先记录一个每行的前缀和，然后运用队列思想求出
然后把所有c*d块的和求出，记为mn数组，方法同上
然后的题目就变成了求每个a*b块-(a-2*b-2)块中每个c*d块的最小值(注意不能贴边)
然而后者我们可以用一个与理想的正方形一模一样的两次单调队列求出
这个循环终值要仔细的推一推
详见代码
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define rep(i,a,b) for(long long i=a;i<=b;i++)
using namespace std;
typedef long long ll;
deque<pair<ll,ll> > Q;
ll n,m,a,b,c,d,map[1050][1050],s[1050][1050],mx[1050][1050],mn[1050][1050],sum,x[1050][1050],y[1050][1050],maxn;
int main(){
scanf("%lld%lld%lld%lld%lld%lld",&m,&n,&a,&b,&c,&d);
rep(i,1,m) rep(j,1,n) scanf("%lld",&map[i][j]),s[i][j]=s[i][j-1]+map[i][j];
rep(j,b,n){
sum=0;
rep(i,0,a-1)sum+=s[i][j]-s[i][j-b];
rep(i,a,m){
sum=sum-s[i-a][j]+s[i-a][j-b];
sum=sum+s[i][j]-s[i][j-b];
mx[i-a+1][j-b+1]=sum;
}
}
rep(j,d,n){
sum=0;
rep(i,0,c-1)sum+=s[i][j]-s[i][j-d];
rep(i,c,m){
sum=sum-s[i-c][j]+s[i-c][j-d];
sum=sum+s[i][j]-s[i][j-d];
mn[i-c+1][j-d+1]=sum;
}
}
rep(i,1,m-c+1){
while(!Q.empty()) Q.pop_back();
rep(j,1,b-d-1){
while(!Q.empty() && Q.back().second>=mn[i][j]) Q.pop_back();
Q.push_back(make_pair(j,mn[i][j]));
}
rep(j,1,n-b+3){
x[i][j]=Q.front().second;
while(!Q.empty() && Q.front().first+(b-d-1)<=b-d+j-1) Q.pop_front();
while(!Q.empty() && Q.back().second>=mn[i][j+b-d-1]) Q.pop_back();
Q.push_back(make_pair(b-d+j-1,mn[i][b-d+j-1]));
}
}
rep(j,1,n-b+3){
while(!Q.empty()) Q.pop_back();
rep(i,1,a-c-1){
while(!Q.empty() && Q.back().second>=x[i][j]) Q.pop_back();
Q.push_back(make_pair(i,x[i][j]));
}
rep(i,1,m-a+3){
y[i][j]=Q.front().second;
while(!Q.empty() && Q.front().first+(a-c-1)<=a-c+i-1) Q.pop_front();
while(!Q.empty() && Q.back().second>=x[i+a-c-1][j]) Q.pop_back();
Q.push_back(make_pair(a-c+i-1,x[a-c+i-1][j]));
}
rep(i,1,m-a+1) rep(j,1,n-b+1) maxn=max(maxn,mx[i][j]-y[i+1][j+1]);
printf("%lld",maxn);
return 0;
}