比赛 |
论文练习 |
评测结果 |
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;
}