661 . 切木板

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

75.0% (3/4)

Tags

apcsc apcsc-ds

Description

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

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

Input Format

輸入第一行是一個整數 N，代表木條數量。
第二行是 N 個空白分隔的整數 a1,a2,…,aN，代表木條長度。

輸入保證 1≤N≤3×105，1≤ai≤109。

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