记录编号	284108	评测结果	AAAAAAAAAA
题目名称	[HAOI 2007]修筑绿化带	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.841 s
提交时间	2016-07-16 21:27:42	内存使用	14.27 MiB

#include<cstdio>
//#include"debug.h"
const int N=1010;
int n,m,a,b,c,d,i,j,ans,s[N][N],v[N][N],dp[N][N],DP[N][N];
int q[N],head,tail;
int main()
{
	freopen("parterre.in","r",stdin);
	freopen("parterre.out","w",stdout);
	scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&d);
	for (i=1;i<=n;i++)
	for (j=1;j<=m;j++){
		scanf("%d",&s[i][j]);
		s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
	}
	for (i=2;i<=n-c;i++)
	for (j=2;j<=m-d;j++)
		v[i][j]=s[i+c-1][j+d-1]-s[i+c-1][j-1]-s[i-1][j+d-1]+s[i-1][j-1];
	//for (i=2;i<=n-c;i++) print(v[i],2,m-d,' ');writeln;
	for (i=2;i<=n-c;i++){
		head=1,tail=0;
		for (j=2;j<=m-d;j++){
			while (head<=tail&&q[head]<=j-b+d+1) head++;
			while (head<=tail&&v[i][q[tail]]>v[i][j]) tail--;
			q[++tail]=j;
			dp[i][j]=v[i][q[head]];
		}
	}
	//for (i=2;i<=n-c;i++) print(dp[i],2,m-d,' ');writeln;
	for (j=2;j<=m-d;j++){
		head=1;tail=0;
		for (i=2;i<=n-c;i++){
			while (head<=tail&&q[head]<=i-a+c+1) head++;
			while (head<=tail&&dp[q[tail]][j]>dp[i][j]) tail--;
			q[++tail]=i;
			DP[i][j]=dp[q[head]][j];
		}
	}
	//for (i=2;i<=n-c;i++) print(DP[i],2,m-d,' ');writeln;
	for (i=1;i<=n-a+1;i++)
	for (j=1;j<=m-b+1;j++){
		int sum=s[i+a-1][j+b-1]-s[i+a-1][j-1]-s[i-1][j+b-1]+s[i-1][j-1];
		sum-=DP[i+a-c-1][j+b-d-1];
		if (sum>ans) ans=sum; 
	}
	printf("%d\n",ans);
	return 0;
}