661 . 切木板

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

66.7% (2/3)

Tags

apcsc apcsc-ds

Description

有一塊高低不平的木板，他是由 $N$ 塊 $1\times a_i$ 由左到右的木條粘接而成的，且底部平整對齊。也就是說，這塊木板佔有的空間是平面區域 $[i,i+1]\times [0,a_i]$$(1\le i \le N)$ 的聯集。

現在想在這塊木板上切出一塊矩形區域，問最大能切出的矩形區域面積為何。

Input Format

輸入第一行是一個整數 $N$，代表木條數量。
第二行是 $N$ 個空白分隔的整數 $a_1, a_2, \dots, a_N$，代表木條長度。

輸入保證 $1\le N\le 3\times 10^ 5$，$1\le a_i\le 10^ 9$。

Output Format

輸出一行一個整數，代表最大能切出的矩形面積。

Sample Input 1

5
3 5 2 1 4

Sample Output 1

6

Sample Input 2

8
2 2 2 2 3 3 3 9

Sample Output 2

16

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~19 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2
1 2000 524288 65536 1 2
2 2000 524288 65536 2
3 2000 524288 65536 2
4 2000 524288 65536 2
5 2000 524288 65536 2
6 2000 524288 65536 2
7 2000 524288 65536 2
8 2000 524288 65536 2
9 2000 524288 65536 2
10 2000 524288 65536 2
11 2000 524288 65536 2
12 2000 524288 65536 2
13 2000 524288 65536 2
14 2000 524288 65536 2
15 2000 524288 65536 2
16 2000 524288 65536 2
17 2000 524288 65536 2
18 2000 524288 65536 2
19 2000 524288 65536 2
Submit
Back to Top