지안지아는 타이완에서의 휴가를 계획하고 있다. 휴가동안 지안지아는 도시에서 도시로 이동하고 도시 안의 관광지들을 방문할 것이다.
타이완에는 하나의 고속도로를 따라서 n 개의 도시들이 위치한다. 이 도시들은 순서대로 0부터 n-1 까지의 번호가 붙어있다. 임의의 i ( 0 < i < n-1 )에 대해서, 도시 i 의 인접한 도시는 도시 i-1 과 i+1 이다. 도시 0과 인접한 도시는 도시 1뿐이고, 도시 n-1 과 인접한 도시는 도시 n-2 뿐이다.
각 도시에는 여러 관광지들이 있다. 지안지아는 d 일 동안의 휴가를 얻었고 가능한 많은 관광지들 을 방문하고 싶다. 지안지아는 휴가를 시작할 도시를 선택했다. 휴가기간동안 매일 지안지아는 인 접한 도시로 움직이거나 또는 현재 도시의 관광지들을 모두 방문한다. 그러나 두 행동을 하 루에 모두 할수는 없다. 지안지아는 한 도시에 여러 번 머물더라도 같은 도시안의 관광지들을 결코 두 번 방문하지는 않는다. 지안지아가 가능한 많은 서로 다른 관광지들을 방문하도록 도와 주자.
도시 | 관광지 개수 |
---|---|
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(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