TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

75.0% (15/20)

Submission's AC Ratio

36.1% (22/61)

Tags

Description

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

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

Input Format

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

Output Format

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

Sample Input 1

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 1

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

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10