TopCoder

User's AC Ratio

93.2% (55/59)

Submission's AC Ratio

54.6% (106/194)

Tags

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

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 1

9

Hints

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

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

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 33
2 1 33
3 2 34

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2500 65536 262144 1
1 2500 65536 262144 2
2 2500 65536 262144 3