比赛 EYOI与SBOI开学欢乐赛11th 评测结果 MMMMMMMMMM
题目名称 矩形地块(A Strip of Land) 最终得分 0
用户昵称 guobinbin 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-10-14 22:24:55
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int m,n,c,h[750][750];
int ini[750][750]={};
int ans=1;
int t;
int mi[750][750][105];
int ma[750][750][105];
int main(){
	freopen("land.in","r",stdin);
	freopen("land.out","w",stdout); 
	scanf("%d%d%d",&m,&n,&c);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&h[i][j]);
		}
		for(int j=1;j<=m;j++){
			for(int k=j;k<=m&&k<=j+99;k++){
				if(k==j||(abs(mi[i][j][k-j]-h[i][k])<=c&&abs(ma[i][j][k-j]-h[i][k])<=c)){
					ini[i][j]++;
					if(k==j){
						mi[i][j][1]=ma[i][j][1]=h[i][j];
					}else{
						mi[i][j][k-j+1]=min(mi[i][j][k-j],h[i][k]);
						ma[i][j][k-j+1]=max(ma[i][j][k-j],h[i][k]);
					}
				}else{
					break;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			t=1;
			while(ini[i][j]>0){
				while(i+t-1<n&&ini[i+t][j]>=ini[i][j]&&ma[i][j][ini[i][j]]-mi[i+t][j][ini[i][j]]<=c&&ma[i+t][j][ini[i][j]]-mi[i][j][ini[i][j]]<=c){
					for(int k=1;k<=ini[i][j];k++){
						ma[i][j][k]=max(ma[i][j][k],ma[i+t][j][k]);
						mi[i][j][k]=min(mi[i][j][k],mi[i+t][j][k]);
					}
					t++;
				}
				ans=max(ans,t*ini[i][j]);
				ini[i][j]--;
				if(i+t-1==n){
					ini[i][j]=0;
				}
			}
		}
	}
	printf("%d",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}