比赛 2022级DP专题练习赛1 评测结果 AAAAAAAAAA
题目名称 棋盘制作 最终得分 100
用户昵称 HeSn 运行时间 2.022 s
代码语言 C++ 内存使用 47.17 MiB
提交时间 2023-02-10 20:54:11
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n, m, a[2010][2010], lft[2010][2010], rgt[2010][2010], up[2010][2010], ans1, ans2; 
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 >> a[i][j];
			lft[i][j] = rgt[i][j] = j;
			up[i][j] = 1;
		}
	}
	for(int i = 1; i <= n; i ++) {
		for(int j = 2; j <= m; j ++) {
			if(a[i][j] != a[i][j - 1]) {
				lft[i][j] = lft[i][j - 1];
			}
		}
	}
	for(int i = 1; i <= n; i ++) {
		for(int j = m - 1; j >= 1; j --) {
			if(a[i][j] != a[i][j + 1]) {
				rgt[i][j] = rgt[i][j + 1];
			}
		}
	}
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= m; j ++) {
			if(i > 1 && a[i][j] != a[i - 1][j]) {
				lft[i][j] = max(lft[i][j], lft[i - 1][j]);
				rgt[i][j] = min(rgt[i][j],rgt[i - 1][j]);
				up[i][j] = up[i - 1][j] + 1;
			}
			int a = rgt[i][j] - lft[i][j] + 1;
			int b = min(a, up[i][j]);
			ans1 = max(ans1, b * b);
			ans2 = max(ans2, a * up[i][j]);
		}
	}
	cout << ans1 << endl << ans2;
	return 0;
}