TopCoder

Thumb   5
Y(OwO)Y
Vanishment This World!!!

User's AC Ratio

93.8% (76/81)

Submission's AC Ratio

46.6% (131/281)

Description

在一個M x N 的區域內,散落了許多不同的障礙物,我們想要知道的是,在這個M x N 的區域內,最大的矩形空地面積是多少?倘若我們用0 與1 表示這個區域內的空地狀況:0 代表這個子區域已被障礙物覆蓋,1 代表這個子區域仍為空地,我們假設每一個0 或1 所代表的子區域面積為1,那麼在下面這個例子中(M=4,N=5),最大的矩形空地為陰影所覆蓋的區域,其面積為8。

在本題中,請依據輸入輸出的規定,針對輸入的地圖,輸出其最大的矩形空地面積。

Input Format

輸入檔第一行有兩個整數,依序為M 和N, M≦200, N≦200;接下來的M 行中,每一行有N 個0 或1 的數字。這N 個數字彼此間用一個空白隔開。

Output Format

請將最大矩形空地面積寫出至輸出檔。

Sample Input

4 5
0 0 1 1 0
0 1 1 1 1
0 1 1 1 1
0 0 1 0 0

Sample Output

8

Hints

Problem Source

原TIOJ1063 / 95北市賽(prob 5)

Subtasks

For Testdata: 0 ~ 0, Score: 12
For Testdata: 1 ~ 1, Score: 12
For Testdata: 2 ~ 2, Score: 12
For Testdata: 3 ~ 3, Score: 12
For Testdata: 4 ~ 4, Score: 12
For Testdata: 5 ~ 5, Score: 12
For Testdata: 6 ~ 6, Score: 12
For Testdata: 7 ~ 7, Score: 16
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536