Description

国际象棋是世界上最古老的博弈游戏之一, 和中国的围棋、象棋以及日本的将棋同享盛名. 据说国际象棋起源于易经的思想, 棋盘是一个 \(8 \times 8\) 大小的黑白相间的方阵, 对应 八八六十四卦, 黑白对应阴阳. 而我们的主人公小 Q, 正是国际象棋的狂热爱好者. 作为 一个顶尖高手, 他已不满足于普通的棋盘与规则, 于是他跟他的好朋友小 W 决定将棋盘扩大以适应他们的新规则. 小 Q 找到了一张由 \(n \times m\) 个正方形的格子组成的矩形纸片, 每个格子被涂有黑白两种颜色之一. 小 Q 想在这种纸中裁减一部分作为新棋盘, 当然, 他希望这个棋盘尽可能的大. 不过小 Q 还没有决定是找一个正方形的棋盘还是一个矩形的棋盘 (当然, 不管哪种, 棋盘必须都黑白相间, 即相邻的格子不同色), 所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积, 从而决定哪个更好一些. 于是小 Q 找到了即将参加全国信息学竞赛的你, 你能帮助他么?

Input

第一行包含两个整数 \(n\) 和 \(m\), 分别表示矩形纸片的长和宽. 接下来的 \(n\) 行包含一个 \(n \times m\) 的 0-1 矩阵, 表示这张矩形纸片的颜色 (0 表示白色, 1 表示黑色).

Output

包含两行, 每行包含一个整数. 第一行为可以找到的最大正方形棋盘的面积, 第二行为可以 找到的最大矩形棋盘的面积 (注意正方形和矩形是可以相交或者包含的).

Sample Input

3 3
1 0 1
0 1 0
1 0 0

Sample Output

4
6

Data Range

对于所有的数据, 满足 \(n, m \leq 2000\)

Explanation

黄学长说的是什么悬线法...... 明明就是高维递推......

话说这种方法我都用了多少年了, 现在才知道有这样一个高大上的名称~

但是把它交到 1052 是怎么回事...... 突然间把我吓到了......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 2010;

int n, m;
int arr[maxn][maxn], // Content of matrix unit
    col_csq[maxn][maxn], // Max consequential choice of units in col, until here
    rlef[maxn][maxn], // Leftest reachable position in row
    rrig[maxn][maxn]; // Rightest reachable position in row
int res_sqr, res_rect;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%d", &arr[i][j]);
            if (i == 1) col_csq[i][j] = 1;
            else if (arr[i][j] != arr[i - 1][j])
                col_csq[i][j] = col_csq[i - 1][j] + 1;
            else
                col_csq[i][j] = 1;
        }
    // Finished data read-in and row-consequential-choice construction.
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            rlef[i][j] = j;
            while (rlef[i][j] > 1 &&
                    col_csq[i][rlef[i][j] - 1] >= col_csq[i][j] &&
                    arr[i][rlef[i][j] - 1] != arr[i][rlef[i][j]])
                rlef[i][j] = rlef[i][rlef[i][j] - 1];
        }
        for (int j = m; j >= 1; j--) {
            rrig[i][j] = j;
            while (rrig[i][j] < m &&
                    col_csq[i][rrig[i][j] + 1] >= col_csq[i][j] &&
                    arr[i][rrig[i][j] + 1] != arr[i][rrig[i][j]])
                rrig[i][j] = rrig[i][rrig[i][j] + 1];
        }
        // Fetching results
        for (int j = 1; j <= m; j++) {
            int height = rrig[i][j] - rlef[i][j] + 1;
            res_rect = max(res_rect, height * col_csq[i][j]);
            height = min(height, col_csq[i][j]);
            res_sqr = max(res_sqr, height * height);
        }
    }
    printf("%d\n%d\n", res_sqr, res_rect);
    return 0;
}