8585: DPL_3_B : Largest Rectangle
[Creator : ]
Description
Given a matrix (H × W) which contains only 1 and 0, find the area of the largest rectangle which only contains 0s.
Input
In the first line, two integers H and W separated by a space character are given.
In the following H lines, $c_{i,j}$, elements of the H × W matrix, are given.
Output
Print the area (the number of 0s) of the largest rectangle.
Constraints
1 ≤ H, W ≤ 1,400
Sample 1 Input
4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0
Sample 1 Output
6