Problem1479--矩阵问题Ⅱ

1479: 矩阵问题Ⅱ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 16  Solved: 10
[Submit] [Status] [Web Board] [Creator:]

Description

给你一个n*m的01矩阵,你可以任意次数地交换矩阵中的任意两列。在完成交换后,你需要在矩阵中选择一个全为1的矩形,请问该矩形的最大面积可以是多少?

Input

第一行两个正整数n和m,n<=1000,m<=1000。
接下来n行,每行m个整数,值只有0和1两种。

Output

输出矩形的最大面积。若无法选择出这样的矩形,输出0。

Sample Input

3 3
1 1 1
1 0 1
0 1 0

Sample Output

4

HINT

对于样例,交换第一列和第二列后变成:
1 1 1
0 1 1
1 0 0
因此我们可以选择右上角的2*2矩形,可以证明再也没有更大的矩形了。

Source/Category