문제 보기 - 휴가 (IOI14_holiday)

시간 제한 메모리 제한 제출 횟수 통과한 사람 수 비율
5000 ms 64 MiB 2731 291 10.66%

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

타이완에는 하나의 고속도로를 따라서 $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일 동안 방문할 수 있는 관광지들의 최대 개수이다.

도시 관광지 개수
010
12
220
330
41
행동
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: 크기 $n$인 배열; $0 \le i \le n-1$에 대해서, attraction[i]는 도시 $i$의 관광지들의 개수.
    • 이 함수는 지안지아가 방문할 수 있는 관광지들의 최대 개수를 리턴해야 한다.

부분 문제

모든 부분 문제에서, $0 \le d \le 2n + \lfloor n/2 \rfloor$이고, 각 도시의 관광지들의 개수는 음이 아닌 정수이다.

추가 제약조건:

부분문제 점수 $n$ 한 도시안의 관광지들의 최대 개수 시작 도시
1 7 $2 \le n \le 20$ 1,000,000,000 제약 없음
2 23 $2 \le n \le 100,000$ 100 0
3 17 $2 \le n \le 3,000$ 1,000,000,000 제약 없음
4 53 $2 \le n \le 100,000$ 1,000,000,000 제약 없음

구현 주의사항

단 하나의 파일을 제출해야 한다. 이름은 holiday.c 혹은 holiday.cpp 이다. 이 파일에는 다음 선언들을 사용해서 위에서 말한 함수가 존재해야 한다. C/C++ 구현에서는 헤더 파일 holiday.h#include해야 한다. 결과가 큰 값일 수 있음에 주의하자. findMaxAttraction의 결과 값의 자료형은 64 비트 정수이다.

long long int findMaxAttraction(int n, int start, int d, int attraction[]);

Sample grader

Sample grader는 다음 형식으로 입력을 받는다:

  • line 1: n, start, d.
  • line 2: attraction[0], ..., attraction[n-1].

Sample grader는 findMaxAttraction의 결과 값을 출력한다.

첨부 파일
파일명 파일 크기
holiday-templates.tar 896.5 KiB