TopCoder

Thumb 1
羽瀨川小鷹
我是布丁

User's AC Ratio

92.6% (163/176)

Submission's AC Ratio

43.8% (271/619)

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

No. Testdata Range Score
1 0 12
2 1 12
3 2 12
4 3 12
5 4 12
6 5 12
7 6 12
8 7 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8