← 返回题目列表

AtCoder · arc081_d

F. 翻转和矩形

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

我们有一个带有 H \times W 网格。 网格中的每个方块都涂成黑色或白色。 i从顶部开始的第行和 j如果左侧的第 列是黑色 j- 第一个字符 S_i is #,如果该字符是白色 ..

Snuke 可以在网格上执行任意次数的以下操作:

  • 在网格中选择一行或一列,然后反转该行或列中所有方块的颜色(即黑色方块变为白色,反之亦然)。

然后,Snuke 沿着网格线绘制一个矩形。这里,矩形中包含的所有正方形都必须涂成黑色。

求当操作执行最佳时 Snuke 矩形的最大可能面积。

约束

  • 2 \leq H \leq 2000
  • 2 \leq W \leq 2000
  • |S_i| = W
  • S_i 包括 # 和 ..

输入

输入由标准输入按以下格式给出:

H W
S_1
S_2
:
S_H

输出

打印 Snuke 矩形的最大可能面积。


示例输入 1

3 3
..#
##.
.#.

示例输出 1

6

如果从上数第一行和从左数第三列反转,则 可以绘制 2 \times 3 矩形,如下图:


示例输入 2

4 4
....
....
....
....

示例输出 2

16

示例输入 3

10 8
##...#.#
##...#.#
..###.#.
#.##.#.#
.#..#.#.
..##.#.#
##.#.#..
...#.#..
###.#.##
###..###

示例输出 3

27