[ARC081F] Flip and Rectangles
题意翻译
给出一个拥有 $H\times W$ 个格子的棋盘,每个格子的颜色为黑色或白色。
Snuke 可以进行任意次下列操作:
- 选择棋盘中的一行或一列,将这一行或一列的颜色翻转(黑变成白,白变成黑)
Snuke 想知道,在他进行操作后,棋盘中最大的全黑矩形最大能为多少。
题目描述
[problemUrl]: https://atcoder.jp/contests/arc081/tasks/arc081_d
$ H\ \times\ W $ のマス目があります. マス目の各マスは黒か白かに塗られており,上から $ i $ 番目,左から $ j $ 番目のマスは,$ S_i $ の $ j $ 文字目が `#` のとき黒マス,`.` のとき白マスです.
すぬけ君は,マス目に対して次の操作を好きな回数行うことができます.
- マス目の任意の行または列を選び,その行または列のすべてのマスの色を反転する (すなわち,黒で塗られたマスを白に,白で塗られたマスを黒に塗り替える).
操作の後,すぬけ君はマス目に沿った長方形を $ 1 $ 個選びます.このとき,選んだ長方形に含まれるすべてのマスは黒で塗られていなければなりません.
うまく操作を行うとき,すぬけ君が選ぶことができる最大の長方形の面積を求めてください.
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ H $ $ W $ $ S_1 $ $ S_2 $ $ : $ $ S_H $
输出格式
すぬけ君が選ぶことができる最大の長方形の面積を出力せよ.
输入输出样例
输入样例 #1
3 3
..#
##.
.#.
输出样例 #1
6
输入样例 #2
4 4
....
....
....
....
输出样例 #2
16
输入样例 #3
10 8
##...#.#
##...#.#
..###.#.
#.##.#.#
.#..#.#.
..##.#.#
##.#.#..
...#.#..
###.#.##
###..###
输出样例 #3
27
说明
### 制約
- $ 2\ \leq\ H\ \leq\ 2000 $
- $ 2\ \leq\ W\ \leq\ 2000 $
- $ |S_i|\ =\ W $
- $ S_i $ は `#`, `.` のみからなる.
### Sample Explanation 1
下図のように,上から $ 1 $ 行目,左から $ 3 $ 列目を反転させると,$ 2\ \times\ 3 $ の長方形を選ぶことができます. !\[\](https://atcoder.jp/img/arc081/2995c3921ed4dffc8ee528b63b9c6118.png)