比赛 论文练习 评测结果 AAAAAAAAAA
题目名称 棋盘制作 最终得分 100
用户昵称 梦那边的美好ET 运行时间 1.474 s
代码语言 C++ 内存使用 95.63 MiB
提交时间 2018-10-19 20:28:22
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int p[2010][2010][2],n,m,bk[2010][2010],f[2010][2010][3],ma1=1,ma2=1;
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++)
			scanf("%d",&bk[i][j]);
	for(int i=1;i<=n;i++){
		p[i][1][0]=1;
	    for(int j=2;j<=m;j++){
		    if(bk[i][j]!=bk[i][j-1])p[i][j][0]=p[i][j-1][0];
			else p[i][j][0]=j;
		}
	}
	for(int i=1;i<=n;i++){
		p[i][m][1]=m;
	    for(int j=m-1;j>=1;j--){
		    if(bk[i][j]!=bk[i][j+1])p[i][j][1]=p[i][j+1][1];
			else p[i][j][1]=j;
		}
	}
	for(int i=1;i<=m;i++){
		f[1][i][0]=1;f[1][i][1]=p[1][i][0];f[1][i][2]=p[1][i][1];
		ma1=max(ma1,(f[1][i][2]-f[1][i][1]+1));
	}
	for(int i=2;i<=n;i++){
	    for(int j=1;j<=m;j++){
		    if(bk[i][j]!=bk[i-1][j]){
				f[i][j][0]=f[i-1][j][0];
				f[i][j][1]=max(p[i][j][0],f[i-1][j][1]);
				f[i][j][2]=min(p[i][j][1],f[i-1][j][2]);
			}
			else{
				f[i][j][0]=i;
				f[i][j][1]=p[i][j][0];
				f[i][j][2]=p[i][j][1];
			}
			ma1=max(ma1,(i-f[i][j][0]+1)*(f[i][j][2]-f[i][j][1]+1));
			ma2=max(ma2,min(i-f[i][j][0]+1,f[i][j][2]-f[i][j][1]+1));
		}
	}
	printf("%d\n",ma2*ma2);printf("%d",ma1);
    return 0;
}