← 返回题目列表

Codeforces · 375/B

B. 最大子矩阵 2

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

给定一个由数字 0 和 1 组成的矩阵,其大小为 n × m。您可以重新排列其行。在给定问题中通过所描述的操作可以获得仅由 1 组成的子矩阵的最大面积是多少?

假设矩阵 a 的行从上到下编号为 1 到 n,列从左到右编号为 1 到 m。第i行和第j列相交处的矩阵单元可以表示为(i,j)。形式上,矩阵 a 的子矩阵是一组四个整数 d、u、l、r (1 ≤ d ≤ u ≤ n;1 ≤ l ≤ r ≤ m)。我们假设子矩阵包含单元 (i, j) (d ≤ i ≤ u; l ≤ j ≤ r)。子矩阵的面积是它包含的单元数。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 5000)。接下来的 n 行每行包含 m 个字符 - 矩阵 a。矩阵a仅包含字符:“0”和“1”。请注意,矩阵的元素后面的行中没有任何空格。

输出

打印单个整数——获得的最大子矩阵的面积。如果我们无法获得数字为 1 的矩阵,则打印 0。

示例

输入 #1

1 1
1

输出 #1

1

输入 #2

2 2
10
11

输出 #2

2

输入 #3

4 3
100
011
000
101

输出 #3

2