Informatica Online Judge

  울타리 자르기 [0969 / 03C9]

Time Limit(Test case) : 100(ms)
Number of users who solved : 127   Total Tried : 216


The Champion of this Problem (C++) : gs17018 - ms / 309byte
My Best Submission (C++) : N/A

[Algospot (JongMan)]

Background

너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있다.

시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했다.

이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶다.

그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여준다.

울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하시오.

단 (c)처럼 직사각형을 비스듬히 잘라낼 수는 없다.

판자의 너비는 모두 1이라고 가정한다.

Input

첫 줄에는 판자의 수 N이 주어진다. 그 다음 줄에는 N개의 정수로 왼쪽부터 각 판자의 높이가 순서대로 주어진다.

[입력값의 정의역]
1 <= N <= 20,000
각 판자의 높이는 10,000이하의 음이 아닌 정수

Output

주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기를 출력한다.

IO Example

입력
7
7 1 5 9 6 7 3

출력
20

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]