比赛 论文练习 评测结果 AAAAAAAAAA
题目名称 棋盘制作 最终得分 100
用户昵称 cool 运行时间 3.142 s
代码语言 C++ 内存使用 18.59 MiB
提交时间 2018-10-19 19:54:59
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define maxn 2010
using namespace std;
int h[maxn],r[maxn],l[maxn];
int n,m;
int ans1=0,ans2=0;
int maxl,maxr;
int Map[maxn][maxn];
int main()
{
	freopen("makechess.in","r",stdin);
	freopen("makechess.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>Map[i][j];
			if((i%2)==(j%2))
			  Map[i][j]=(!Map[i][j]);
		}
	//1
	for(int i=1;i<=m;i++)
		r[i]=m;
	for(int i=1;i<=n;i++)
	{
    	maxl=1,maxr=m;
    	for(int j=1;j<=m;j++)
    	{
			if(Map[i][j])
			{
				maxl=j+1;
				h[j]=l[j]=0;
			}
			else
			{
				h[j]++;
				l[j]=max(l[j],maxl);
			}
			
		}
		for(int j=m;j>=1;j--)
		{
			if(Map[i][j])
			{
				maxr=j-1;
				r[j]=m;
			}
			else
			{
				r[j]=min(r[j],maxr);
				int rr=min(r[j]-l[j]+1,h[j]);
				ans1=max(ans1,rr*rr);
				ans2=max(ans2,(r[j]-l[j]+1)*h[j]);
			}
		}
	}	
	memset(r,0,sizeof(r));memset(h,0,sizeof(h));memset(l,0,sizeof(l));
	for(int i=1;i<=m;i++)
		r[i]=m;
	for(int i=1;i<=n;i++)
	{
    	maxl=1,maxr=m;
    	for(int j=1;j<=m;j++)
    	{
			if(!Map[i][j])
			{
				maxl=j+1;
				h[j]=l[j]=0;
			}
			else
			{
				h[j]++;
				l[j]=max(l[j],maxl);
			}
			
		}
		for(int j=m;j>=1;j--)
		{
			if(!Map[i][j])
			{
				maxr=j-1;
				r[j]=m;
			}
			else
			{
				r[j]=min(r[j],maxr);
				int rr=min(r[j]-l[j]+1,h[j]);
				ans1=max(ans1,rr*rr);
				ans2=max(ans2,(r[j]-l[j]+1)*h[j]);
			}
		}
	}
	cout<<ans1<<"\n"<<ans2<<"\n";
	return 0;
}