记录编号	174629	评测结果	AAAAAAAAAA
题目名称	658.[ZJOI 2007] 棋盘制作	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	2.851 s
提交时间	2015-08-02 06:22:13	内存使用	41.54 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int a[2001][2001],map[2001][2001],t;
int maxp[2001][2001],n,m,l[2001],r[2001];
int maxn=0,w,ans1,ans2;
inline int in()
{
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9')c=getchar();
	for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';
	return x;
}
int day(int yu){
	return yu*yu;
}
int work1(int yu){
	maxn=0;
	memset(map,0,sizeof(map));
	 for(int i=1;i<=m;++i){
		for(int j=1;j<=n;++j){
			if(a[j][i]==yu)
			   map[j][i]=map[j-1][i]+1;
			 else
			    map[j][i]=0;
		}
	}
	for(int i=1;i<=n;++i){
		l[1]=1,r[m]=m;
		for(int j=2;j<=m;++j){
			if(!map[i][j]) continue;
			 t=j;
			 while(t>1&&map[i][j]<=map[i][t-1])
			   t=l[t-1];
			 l[j]=t;
			}
			for(int j=m-1;j>=1;--j){
			if(!map[i][j]) continue;
			   t=j;
			while(t<m&&map[i][j]<=map[i][t+1])
			  t=r[t+1];
			r[j]=t;
		}
		  for(int j=1;j<=m;++j){
			if((r[j]-l[j]+1)*map[i][j]>maxn){
				 maxn=(r[j]-l[j]+1)*map[i][j];
			}
		}
		}
	return maxn;
}
int work2(int yu){
	maxn=0;
	memset(map,0,sizeof(map));
	for(int i=1;i<=m;++i){
		for(int j=1;j<=n;++j){
			if(a[j][i]==yu)
			   map[j][i]=map[j-1][i]+1;
			else
			  map[j][i]=0;
		}
	}
	for(int i=1;i<=n;++i){
		l[1]=1,r[m]=m;
		for(int j=2;j<=m;++j){
			if(!map[i][j]) continue;
			 t=j;
			 while(t>1&&map[i][j]<=map[i][t-1])
			   t=l[t-1];
			 l[j]=t;
			}
		 for(int j=m-1;j>=1;--j){
			if(!map[i][j]) continue;
			t=j;
			while(t<m&&map[i][j]<=map[i][t+1])
			  t=r[t+1];
			r[j]=t;
		}
		 for(int j=1;j<=m;++j){
			if(day(min((r[j]-l[j]+1),map[i][j]))>maxn){
				 maxn=day(min((r[j]-l[j]+1),map[i][j]));
			}
		  }
		}
	return maxn;
}
int main()
{   freopen("makechess.in","r",stdin);
    freopen("makechess.out","w",stdout);
	n=in(),m=in();
	for(int i=1;i<=n;++i)
	  for(int j=1;j<=m;++j)
	  	{
		  a[i][j]=in();
		  if(i%2!=j%2)//巧妙的转化为全0/1矩阵，借用了大神们的证明； 
		    a[i][j]=1-a[i][j];
	  	}
	ans1=max(work1(1),work1(0));
	ans2=max(work2(1),work2(0));
	printf("%d\n%d",ans2,ans1);
}