记录编号	174841	评测结果	AAAAAAAAAA
题目名称	658.[ZJOI 2007] 棋盘制作	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	2.699 s
提交时间	2015-08-03 07:36:27	内存使用	61.63 MiB

#define Max(a,b)((a)>(b)?(a):(b))
#define Min(a,b)((a)<(b)?(a):(b))
 
#include<cstdio>
 
using namespace std;
 int temp;
char s;
inline int in()
{
	temp=0;s=getchar();
	while(s<48||s>57)
		s=getchar();
	for(;s>=48&&s<=57;s=getchar())
		temp=temp*10+s-48;
	return temp;
}
 
int n,m,smax[2005][2005],a[2005][2005];
int rmax[2005][2005],xmax[2005][2005],z,c;
 
int main()
{
    freopen("makechess.in","r",stdin);
    freopen("makechess.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=in();
    for(int i=1;i<=n;i++)
    {
        int head=1,tail=1;
        while(head<=m)
        {    
             while(head>tail)tail++;
             while(head<=tail&&a[i][tail+1]^a[i][tail]&&tail+1<=m)tail++;  
             rmax[i][head]=tail;head++;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int head=1,tail=1;
        while(head<=n)
        {     
            while(head>tail)tail++;   
            while(head<=tail&&a[tail][i]^a[tail+1][i]&&tail+1<=n)tail++;      
            xmax[head][i]=tail;head++;
        }
        head=tail=n;
        while(head>=1)
        {
            while(head<tail)tail--;
            while(head>=tail&&a[tail][i]^a[tail-1][i]&&tail-1>=1)tail--;
            smax[head][i]=tail;head--;
        }
    }
    
    for(int i=1;i<=m;i++)
    {
        int q[2000]={0};int head=1,tail=0,k[2005]={0};
        for(int j=1;j<=n;j++)
        {
            while(head<=tail&&q[head]<smax[j][i])head++;
            while(head<=tail&&rmax[j][i]<=rmax[q[tail]][i])tail--;
            if(head<=tail)k[j]=q[tail]+1;//!!!!
            else k[j]=smax[j][i];  
            q[++tail]=j;
        }
        head=1;tail=0;
        for(int j=n;j>=1;j--)
        {
            while(head<=tail&&q[head]>xmax[j][i])head++;
            while(head<=tail&&rmax[j][i]<=rmax[q[tail]][i])tail--;
            if(head<=tail) 
            {
                c=Max(c,(q[tail]-k[j])*(rmax[j][i]-i+1));//!!!!
                z=Max(z,Min(q[tail]-k[j],rmax[j][i]-i+1)*Min(q[tail]-k[j],rmax[j][i]-i+1));
            }
            else
            {
                c=Max(c,(xmax[j][i]-k[j]+1)*(rmax[j][i]-i+1));
                z=Max(z,Min(xmax[j][i]-k[j]+1,rmax[j][i]-i+1)*Min(xmax[j][i]-k[j]+1,rmax[j][i]-i+1));
            }
            q[++tail]=j;
        }
    }
    printf("%d\n%d",z,c);
}