比赛 2022级DP专题练习赛1 评测结果 AAAAAAAAAA
题目名称 棋盘制作 最终得分 100
用户昵称 遥时_彼方 运行时间 0.379 s
代码语言 C++ 内存使用 41.92 MiB
提交时间 2023-02-10 20:57:53
显示代码纯文本
#include<bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define drep(x,y,z) for(int x=y;x>=z;x--)
#define ull unsigned long long
#define ll long long
using namespace std;
inline int read()
{
	int x=0;bool flag=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')flag=0;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	if(flag) return x;
	return ~(x-1);
}
inline void write(int x)
{
	if(x<0) {x=~(x-1);putchar('-');}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
////////////////////////
const int N=2e3+50; 
int nc,mc;
int a[N][N];
int l[N][N],r[N][N],u[N][N];
int ans1,ans2;
int main()
{
    freopen("makechess.in","r",stdin);
	freopen("makechess.out","w",stdout);
	nc=read(),mc=read();
	int s1;
	rep(i,1,nc)
		rep(o,1,mc) a[i][o]=read(),u[i][o]=1;
	rep(i,1,nc)
	{
		l[i][1]=1;
		rep(o,2,mc)
		{
			if(a[i][o-1]^a[i][o]) l[i][o]=l[i][o-1];
			else l[i][o]=o;
		}
	}
	rep(i,1,nc)
	{
		r[i][mc]=mc;
		drep(o,mc-1,1)
		{
			if(a[i][o+1]^a[i][o]) r[i][o]=r[i][o+1];
			else r[i][o]=o;
			ans2=max(ans2,r[i][o]-l[i][o]+1);
//			cout<<i<<" "<<o<<":"<<r[i][o]<<" "<<l[i][o]<<endl;
		}
	}
	ans1=1;
	rep(i,2,nc)
	{
		rep(o,1,mc)
		{
			if(a[i][o]^a[i-1][o])
			{
				u[i][o]+=u[i-1][o];
				l[i][o]=max(l[i][o],l[i-1][o]);
				r[i][o]=min(r[i][o],r[i-1][o]);
			}
			s1=min(r[i][o]-l[i][o]+1,u[i][o]);
			ans1=max(ans1,s1*s1);
			ans2=max(ans2,(r[i][o]-l[i][o]+1)*u[i][o]);
		}
	}
	write(ans1);
	putchar(10);
	write(ans2);
	putchar(10);
    return 0;
}