[ZJOI2007]棋盘制作

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+7;
typedef long long ll;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int res[maxn][maxn],lt[maxn][maxn],rt[maxn][maxn],height[maxn][maxn],ans,ans2;
int main() {
    int n=read(),m=read();
    for(int i=1; i<=n; ++i) {
        for(int j=1; j<=m; ++j) {
            res[i][j]=read();
            lt[i][j]=rt[i][j]=j;
            height[i][j]=1;
        }
    }

    for(int i=1;i<=n;++i)
    for(int j=2;j<=m;++j)
        if(res[i][j]!=res[i][j-1]) lt[i][j]=lt[i][j-1];

    for(int i=1;i<=n;++i)
    for(int j=m-1;j;--j)
        if(res[i][j]!=res[i][j+1]) rt[i][j]=rt[i][j+1];

    for(int i=1;i<=n;++i)
    for(int j=1,a,b;j<=m;++j) {
        if(i>1&&res[i][j] != res[i - 1][j]) {
            lt[i][j]=max(lt[i][j],lt[i - 1][j]);
            rt[i][j]=min(rt[i][j],rt[i - 1][j]);
            height[i][j] = height[i - 1][j] + 1;
        }
        a=rt[i][j]-lt[i][j]+1;
        b=min(a,height[i][j]);
        ans=max(b*b,ans);
        ans2=max(ans2,a*height[i][j]);
    }
    printf("%d\n%d",ans,ans2);
    return 0;
}