Informatica Online Judge

  수력발전소 (L) [1138 / 0472]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 19   Total Tried : 38


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

[Codeforces.com 변경]

Background

이번에 경곽이는 수력발전에 대해서 배우고, 주어진 환경에서 최대한 효과를 볼 수 있도록 수력발전소위치를 선정하고자 한다.

수력발전소의 효율은 수력발전소가 설치된 영역 내부의 각 영역의 높이차가 클수록 높다.

만약 수력발전소의 크기가 5 이고, 발전소가 위치한 5군데 영역의 높이의 최댓값과 최솟값의 차이가 그 발전소의 발전량이 된다.

길이가 n인 강이 주어진다. 강의 각 영역에 원하는 만큼의 수의 발전소원하는 크기로 설치할 수 있다.

예를 들어 강의 길이가 6 이고, 강의 각 영역의 높이가 다음과 같다면,

2 1 2 3 1 2

크기가 2인 발전소 2개를 다음과 같이 설치한다고 가정하자.

2 [ 1, 2 ] [ 3, 1 ] 2

빨간색 발전소의 발전량은 최댓값 2 최솟값 1이므로 발전량은 1이다.

파란색 발전소의 발전량은 최댓값 3 최솟값 1이므로 발전량은 2이다.

따라서 전체 발전량은 3이 된다.

물론 다음과 같이 발전량이 3인 경우도 만들 수 있다.

2 [ 1 2 3 ] [ 1 2 ]

이 경우에는 크기가 3인 발전소 1개와 크기가 2인 발전소 1개를 만든 것이다.

이 때 크기가 3인 발전소의 발전량은 2, 크기가 2인 발전소의 발전량은 1 이므로 전체 발전량은 3이다.

하지만 어떤 방법으로 발전소를 건설하더라도 3보다 더 많은 양의 발전소를 설치할 수는 없다.

따라서 주어진 강에서는 최대 3의 전기를 생산할 수 있다.

강의 크기와 강의 각 영역의 높이값이 주어질 때 최대 발전량을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 강의 크기를 나타내는 수 n을 입력한다.

다음 줄에 각 영역의 높이를 나타내는 수가 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= n <= 1,000,000
각 영역의 높이 10^9

Output

원하는 수의 발전소를 원하는 크기만큼 설치한 후의 최대 발전량을 출력한다.

IO Example

입력
6
2 1 2 3 1 2

출력
3

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