TopCoder

M_SQRT
$\textbf{W}\symbfit{elcome~to~}\Huge\color{blue}{\mathbfcal{TIOJ}}%Caidorz$

User's AC Ratio

91.6% (261/285)

Submission's AC Ratio

45.1% (435/964)

Tags

Description

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

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

Input Format

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

Output Format

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

Sample Input 1

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

Sample Output 1

8

Hints

Problem Source

原TIOJ1063 / 95北市賽(prob 5)
2021.03.21 Update: Added $\LaTeX$ by FHVirus

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 (VSS, 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