TopCoder

User's AC Ratio

57.1% (4/7)

Submission's AC Ratio

30.8% (4/13)

Description

一塊N*M單位方格大小的區域中,每一單位都有一個高度。

請你找一塊面積最大的矩形子區域,使得這一個區域中的任一格,其左方(若在該區域中)以及上方(若在該區域中)的高度皆小於該格的高度。

Input Format

輸入的第一行有兩個整數N,M。
接下來有N行每行有M個以空格隔開的整數。

Output Format

請輸出符合條件的最大面積。

Sample Input

5 5
2 1 4 3 5
2 4 3 3 1
3 1 2 4 5
2 3 4 5 1
3 4 2 6 5

Sample Output

6

Hints

範例輸入中,大小為6的最大矩形子區域為
1 2 4
3 4 5

1<=N,M<=100
-1,000,000,000<=所有高度值<=1,000,000,000

Problem Source

原TIOJ1470 / CSAPC'08 Problem Setter: Tmt

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 3000 65536
1 3000 65536
2 3000 65536
3 3000 65536
4 3000 65536
5 3000 65536
6 3000 65536
7 3000 65536
8 3000 65536
9 3000 65536