AtCoder Regular Contest 081
F
Flip and Rectangles
AtCoder
⌀ 2608
原题
← E→
翻译中…

Problem Statement

翻译中…

We have a board with an $H \times W$ grid. Each square in the grid is painted in black or white. The square at the $i$-th row from the top and $j$-th column from the left is black if the $j$-th character in $S_i$ is #, and white if that character is ..

翻译中…

Snuke can perform the following operation on the grid any number of times:

翻译中…
  • Select a row or column in the grid, and invert the color of all the squares in that row or column (that is, black squares become white and vice versa).
翻译中…

Then, Snuke draws a rectangle along grid lines. Here, all the squares contained in the rectangle must be painted in black.

翻译中…

Find the maximum possible area of Snuke's rectangle when the operation is performed optimally.

翻译中…

Constraints

翻译中…
  • $2 \leq H \leq 2000$
  • $2 \leq W \leq 2000$
  • $|S_i| = W$
  • $S_i$ consists of # and ..
翻译中…

Input

翻译中…

Input is given from Standard Input in the following format:

翻译中…

H W
S_1
S_2
:
S_H

翻译中…

Output

翻译中…

Print the maximum possible area of Snuke's rectangle.

翻译中…

样例

Input #1
3 3
..#
##.
.#.
Output #1
6
If the first row from the top and the third column from the left are inverted, a $2 \times 3$ rectangle can be drawn, as shown below: ![image](https://atcoder.jp/img/arc081/2995c3921ed4dffc8ee528b63b9c6118.png)
Input #2
4 4
....
....
....
....
Output #2
16
Input #3
10 8
##...#.#
##...#.#
..###.#.
#.##.#.#
.#..#.#.
..##.#.#
##.#.#..
...#.#..
###.#.##
###..###
Output #3
27
题目信息
题号
arc081_d
时间限制
2 s
内存限制
256 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。