TopCoder

User's AC Ratio

90.0% (18/20)

Submission's AC Ratio

60.9% (28/46)

Description

在一塊大小為M*N單位方格的土地上,每一個單位格子可能適合(標記為0),或不適合(標記為1)用於建築。
對於某個矩形範圍X,若範圍X裡面適合建築的格子數比不適合建築的格子數多,我們就說個矩形範圍X適合蓋房子。
請問最大能蓋多大面積的房子呢?

Input Format

輸入的第一列有一個正整數T(1<=T<=20)代表接下來測試資料的組數。
每筆測試資料的第一列有兩個正整數N,M(1<=N,M<=200)代表地圖的長寬,
然後有N列每列M個以空白隔開的0或1代表這格適合,或不適合用來蓋房子。

Output Format

對於每筆測試資料請輸出一個整數代表最大可建築面積。

Sample Input

1
5 5
0 1 0 0 1
1 0 1 1 1
0 0 1 1 0
0 1 1 0 1
1 1 0 1 0

Sample Output

9

Hints

在上面的範例中,左上角3*3的範圍是最大適合蓋房子的區域。

※最大的測試資料(i.e. 200*200大小的地圖)只有兩筆。

Problem Source

原TIOJ1134 / 96 TWN Practice Contest 1。Problem Setter: Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 33
For Testdata: 1 ~ 1, Score: 33
For Testdata: 2 ~ 2, Score: 34
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2500 65536 65536
1 2500 65536 65536
2 2500 65536 65536