시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 896 | 446 | 348 | 52.968% |
JOI 군과 IOI 양은 쌍둥이 남매이다. JOI 군은 최근 과자 만들기에 푹 빠졌기 때문에, JOI 군은 오늘도 케이크를 만들어서 먹으려고 했지만, 막 구워진 참에 냄새를 맡고 온 IOI 양이 왔기 때문에 두 명이 케이크를 나누어 먹기로 했다.
케이크는 둥그런 모양을 하고 있다. 어느 점에서부터 직선으로 칼집을 넣어 케이크를 N 개의 조각으로 나눈 뒤, 각 조각마다 1부터 N 까지 반시계방향으로 번호를 매긴다. 즉, 1 ≦ i ≦ N에 대해, i 번째 조각은 i - 1 번째와 i + 1 번째 조각과 인접해있다. (단, 0번째는 N 번째, N + 1 번째는 1번째로 간주한다). i 번째 조각의 크기는 Ai 이지만, 칼질이 서툴러 Ai가 모두 다른 값을 가지게 되었다.
그림 1 : 케이크의 예 (N = 5, A1 = 2, A2 = 8, A3 = 1, A4 = 10, A5 = 9)
이 N개를 JOI 군과 IOI 양이 나누기로 하였다. 나누는 방법은 다음과 같다.
JOI 군은 자신이 가져온 조각들 크기의 합을 최대화하고 싶다.
케이크의 조각 수 N 과, N 개의 조각의 크기에 대한 정보가 주어질 때, JOI 군이 가져올 수 있는 조각들의 합계의 최대치를 구하는 프로그램을 작성하시오.
표준입력으로부터 이하의 입력이 주어진다.
JOI 군이 가져올 수 있는 조각들의 합계의 최대치를 한 줄로 출력하시오.
번호 | 배점 | 제한 |
---|---|---|
1 | 15 | N ≦ 20 |
2 | 45 | N ≦ 300 |
3 | 40 | 추가적인 제약 조건이 없다. |
5 2 8 1 10 9
18
JOI 군이 다음과 같은 순서로 케이크를 가져오는 것이 최적해이다.
최종적으로, JOI 군이 가져온 조각들 크기의 합계는 8+9+1 = 18이 된다.
8 1 10 4 5 6 2 9 3
26
15 182243672 10074562 977552215 122668426 685444213 3784162 463324752 560071245 134465220 21447865 654556327 183481051 20041805 405079805 564327789
3600242976
Olympiad > Japanese Olympiad in Informatics > JOI 2014/2015 2번