KOI 1차 2021 중1- 꿀 따기 > 문제은행 : 정보올림피아드&알고리즘




4726 : 꿀 따기

제한시간
1000 ms   
메모리제한
512 MB   
해결횟수
41 회   
시도횟수
132 회   

문제

아래와 같이 좌우로 N개의 장소가 있다.


 

 

장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둔다.

또, 다른 한 장소를 골라서 벌통을 둔다.

아래 그림에서 연한 회색의 장소는 벌이 있는 장소이고 진한 회색의 장소는 벌통이 있는 장소이다.

 

 

두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 딴다.

각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양이다.

1. 두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다.(벌통이 있는 장소에서도 같다.)

2. 벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.

위의 그림과 같이 배치된 경우 두 마리의 벌 모두 4 + 1 + 4 + 9 + 9 = 27의 꿀을 따서, 전체 꿀의 양은 54가 된다.

 

위의 그림과 같이 배치된 경우 왼쪽 장소에서 출발한 벌은 9 + 4 + 4 + 9 + 9 = 35의 꿀을 따고 

오른쪽 장소에서 출발한 벌은 4 + 9 + 9 = 22의 꿀을 따므로,

전체 꿀의 양은 57이 된다.

 

 

위의 그림과 같은 경우는 전체 꿀의 양이 31이 된다.

장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.

 

[제약 조건]

* 3 ≤​ N ≤​ 100,000

* 각 장소의 꿀의 양은 1 이상 10,000 이하의 정수이다.

 

[부분 문제]

1. (11점) N ≤ 20

2​. (13점) N ≤ ​500

3​. (31점) N ≤ ​5,000

4​. (45점) 추가적인 제한이 없음.

 

 

 


입력형식

첫 번째 줄에 장소의 수 N이 주어진다.

다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다.


출력형식

첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다.


입력 예

7
9 9 4 1 4 9 9

출력 예

57

입력 예

19
10 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 5 10

출력 예

65

입력 예

3
2 5 4

출력 예

10

데이타 만든사람 : ohjtgood

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP