IOI 2014 day2 3- 휴가(holiday) > 문제은행 : 정보올림피아드&알고리즘




3511 : 휴가(holiday)

제한시간
5000 ms   
메모리제한
64 MB   
해결횟수
1 회   
시도횟수
7 회   

문제

지안지아는 타이완에서의 휴가를 계획하고 있다. 

휴가동안 지안지아는 도시에서 도시로 이동하고 도시 안의 관광지들을 방문할 것이다.

 

타이완에는 하나의 고속도로를 따라서 n개의 도시들이 위치한다. 

이 도시들은 순서대로 0부터 n−1까지의 번호가 붙어있다. 

임의의 i (0<i<n−1)에 대해서, 도시 i의 인접한 도시는 도시 i−1과 i+1이다. 

도시 0과 인접한 도시는 도시 1뿐이고, 도시 n−1과 인접한 도시는 도시 n−2뿐이다.

 

각 도시에는 여러 관광지들이 있다. 

지안지아는 d일 동안의 휴가를 얻었고 가능한 많은 관광지들을 방문하고 싶다. 

지안지아는 휴가를 시작할 도시를 선택했다. 

휴가기간동안 매일 지안지아는 인접한 도시로 움직이거나 또는 현재 도시의 관광지들을 모두 방문한다. 

그러나 두 행동을 하루에 모두 할수는 없다. 

지안지아는 한 도시에 여러 번 머물더라도 같은 도시안의 관광지들을 결코 두 번 방문하지는 않는다. 

지안지아가 가능한 많은 서로 다른 관광지들을 방문하도록 도와주자.

 

[예제]

지안지아는 7일의 휴가를 얻었고, (아래 표와 같이) 5개의 도시가 있고 도시 2에서 휴가를 시작하였다. 

첫 번째 날 지안지아는 도시 2의 20개 관광지를 방문한다. 

두 번째 날 지안지아는 도시 2에서 도시 3으로 이동하고 세 번째 날 도시 3의 30개 관광지들을 방문한다. 

다음 3일동안 지안지아는 도시 3에서 도시 0으로 이동해서 일곱 번째 날에 도시 0의 10개 관광지들을 방문한다. 

따라서지안지아가 방문한 관광지의 총 개수는 20 + 30 + 10 = 60이고 

이것은 그가 도시 2에서 시작해서 7일 동안 방문할 수 있는 관광지들의 최대 개수이다.

 

 도시

 관광지 개수

 0

 10

 1

 2

 2

 20

 3

 30

 4

 1

 

 

 일

 행동

 1

 도시 2의 관광지들을 방문​

 2

 도시 2에서 도시 3으로 이동​

 3

 도시 3의 관광지들을 방문​

 4

 도시 3에서 도시 2로 이동​

 5

 도시 2에서 도시 1로 이동​

 6

 도시 1에서 도시 0으로 이동​

 7

 도시 0의 관광지들을 방문​

 

지안지아가 방문할 수 있는 관광지들의 최대 개수를 계산하시오.​ 


입력형식

첫째 줄에 도시의 개수 n, 시작 도시의 번호 start, 휴가일의 수 d가 주어진다. (2 ≤ n ≤ 100,000)

둘째 줄에는 도시 i의 관광지 개수가 0번 도시부터 순서대로 공백으로 구분해 주어진다. 

한 도시 안의 관광지들의 최대 개수는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다. 또, 0 ≤ d ≤ 2n + ⌊n/2⌋를 만족한다.


출력형식

지안지아가 방문할 수 있는 관광지의 최대 개수를 출력한다.

입력 예

5 2 7
10 2 20 30 1

출력 예

60


DCO (Divide and Conquer Optimization)

경기도 안양시 동안구 평촌대로 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