시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 443 | 241 | 189 | 57.975% |
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 군이 가져올 수 있는 조각들의 합계의 최대치를 한 줄로 출력하시오.
5 2 8 1 10 9
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
JOI 군이 다음과 같은 순서로 케이크를 가져오는 것이 최적해이다.
최종적으로, JOI 군이 가져온 조각들 크기의 합계는 8+9+1 = 18이 된다.
Olympiad > 일본정보올림피아드 > JOI 2015 2번