프로그램 명: ioi_holliday
제한시간: 1 초

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

타이완에는 하나의 고속도로를 따라서 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 의 관광지들을 방문

문제

지안지아가 방문할 수 있는 관광지들의 최대 개수를 계산하는 함수 findMaxAttraction을 구현 하시오.
findMaxAttraction(n, start, d, attraction)
n: 도시들의 개수.
start: 시작 도시의 번호.
d: 휴가일의 개수.
attraction: 크기 인 배열; 에 대해서, attraction[i]는 도시 의
관광지들의 개수.
이 함수는 지안지아가 방문할 수 있는 관광지들의 최대 개수를 리턴해야 한다.

ample grader
Sample grader는 다음 형식으로 입력을 받는다:
line 1: n, start, d.
line 2: attraction[0], ..., attraction[n-1].
Sample grader는 findMaxAttraction의 결과 값을 출력한다

입력

출력

입출력 예

입력

출력

출처: International Olympiad in Informatics 2014 day 2

[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]