Informatica Online Judge

  도넛 [0963 / 03C3]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 57   Total Tried : 379


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

[笠浦一海]

Background

도넛을 매우 좋아하는 경곽이는 경희, 경숙이의 2명의 여동생이 있다.

경곽이는 두 여동생을 매우 아끼기로 유명하다.

오늘 간식으로 매우 큰 특이한 도넛이 준비되었다. 경곽이는 도넛을 매우 좋아하므로 되도록이면 많이 먹고자 하지만, 두 동생을 아끼는 마음이 더 커서 두 동생에게 더 많은 도넛을 주고자 한다.

경곽이는 도넛을 자를 칼을 가지고 있다. 하지만 도넛이 특이해서 지정된 곳이 아닌 다른 곳을 자르면 다 부서져서 먹을 수 없는 상태가 된다.

경곽이는 아래 그림과 같이 도넛에 n개 군데 자를 수 있는 위치를 알고 있다.



자를 수 있는 위치는 1~n으로 이 중 3곳을 잘라야 3등분 할 수 있다.

자를 위치 i와 i+1사이에 위치한 부분의 크기를 A_i라 한다. 단 n과 1번 위치 사이의 부분은 A_n이다.

경곽이는 두 동생들 각각에게 자신이 먹는 양 이상 많은 양의 도넛을 주면서 자신이 먹을 수 있는 양을 최대화 하고자 한다. 이를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 자를 수 있는 위치의 수 n이 주어진다.
두 번째 줄부터 n줄에 걸쳐서 각 부분의 크기 a_i가 주어진다.

[입력값의 정의역]
3 <= n <= 100,000
1 <= a_i <= 1,000,000

[부분점수 조건]
[50%의 데이터는 n이 500 이하의 값이다.]

Output

경곽이가 먹을 수 있는 최대량을 출력한다.

IO Example

입력
6
1
5
4
5
2
4

출력
6

[해설]

A1, A2 = 6
A3, A4 = 9
A5, A6 = 6

으로 자를 수 있고 , 이 때 경곽이는 6을 먹을 수 있으므로 최대가 된다.

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