10714번 - 케이크 자르기 2

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 64 43 35 70.000%

문제

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 양이 나누기로 하였다. 나누는 방법은 다음과 같다.

  1. 먼저, JOI 군이 N 개의 조각 중 원하는 것 하나를 가져간다.
  2. 그 뒤, IOI 양으로부터 시작해 IOI 양과 JOI 군은 번갈아가며 남은 조각을 하나씩 가져간다. 단, 인접한 조각 중 하나 이상의 조각이 이미 선택된 경우에만 가져갈 수 있다. 가져갈 수 있는 조각이 여러 개 있을 때엔, IOI 양은 그 중 가장 큰 조각을 가져가고, JOI 군은 원하는 조각을 가져갈 수 있다.

JOI 군은 자신이 가져온 조각들 크기의 합을 최대화하고 싶다.

케이크의 조각 수 N 과, N 개의 조각의 크기에 대한 정보가 주어질 때, JOI 군이 가져올 수 있는 조각들의 합계의 최대치를 구하는 프로그램을 작성하시오.

입력

표준입력으로부터 이하의 입력이 주어진다.

  • 첫번째 줄에는 케이크가 N 개의 조각으로 나뉘어 있음을 나타내는 정수 N이 주어진다.
  • 이어지는 N 열 중 i 열 (1 ≦ i ≦ N) 에는 i 번째 조각의 크기를 나타내는 정수 Ai가 적혀있다.

모든 입력 데이터는 아래의 조건을 만족한다.

  • 1 ≦ N ≦ 2 000．
  • 1 ≦ Ai ≦ 1 000 000 000．
  • Ai 모두 다른 값을 갖는다.

출력

JOI 군이 가져올 수 있는 조각들의 합계의 최대치를 한 줄로 출력하시오.

예제 입력 1 

5
2
8
1
10
9

예제 출력 1 

18

예제 입력 2 

8
1
10
4
5
6
2
9
3

예제 출력 2 

26

예제 입력 3 

15
182243672
10074562
977552215
122668426
685444213
3784162
463324752
560071245
134465220
21447865
654556327
183481051
20041805
405079805
564327789

예제 출력 3 

3600242976

힌트

JOI 군이 다음과 같은 순서로 케이크를 가져오는 것이 최적해이다.

  1. JOI 군이 2번째 조각을 가져온다. 이 조각의 크기는 8이다.
  2. IOI 양은 1번째 조각을 가져온다. 이 조각의 크기는 2이다.
  3. JOI 군이 5번째 조각을 가져온다. 이 조각의 크기는 9이다.
  4. IOI 양은 4번째 조각을 가져온다. 이 조각의 크기는 10이다.
  5. JOI 군이 3번째 조각을 가져온다. 이 조각의 크기는 1이다.

최종적으로, JOI 군이 가져온 조각들 크기의 합계는 8+9+1 = 18이 된다.

W3sicHJvYmxlbV9pZCI6IjEwNzE0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjZjAwXHVjNzc0XHVkMDZjIFx1Yzc5MFx1Yjk3NFx1YWUzMCAyIiwiZGVzY3JpcHRpb24iOiI8cD5KT0kgXHVhZDcwXHVhY2ZjIElPSSBcdWM1OTFcdWM3NDAgXHVjMzBkXHViNDY1XHVjNzc0IFx1YjBhOFx1YjllNFx1Yzc3NFx1YjJlNC4gSk9JIFx1YWQ3MFx1Yzc0MCBcdWNkNWNcdWFkZmMgXHVhY2ZjXHVjNzkwIFx1YjljY1x1YjRlNFx1YWUzMFx1YzVkMCBcdWQ0NzkgXHViZTYwXHVjODRjXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgSk9JIFx1YWQ3MFx1Yzc0MCBcdWM2MjRcdWIyOThcdWIzYzQgXHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjIFx1YjljY1x1YjRlNFx1YzViNFx1YzExYyBcdWJhMzlcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTg4XHVjOWMwXHViOWNjLCBcdWI5YzkgXHVhZDZjXHVjNmNjXHVjOWM0IFx1Y2MzOFx1YzVkMCBcdWIwYzRcdWMwYzhcdWI5N2MgXHViOWUxXHVhY2UwIFx1YzYyOCBJT0kgXHVjNTkxXHVjNzc0IFx1YzY1NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViNDUwIFx1YmE4NVx1Yzc3NCBcdWNmMDBcdWM3NzRcdWQwNmNcdWI5N2MgXHViMDk4XHViMjA0XHVjNWI0IFx1YmEzOVx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2YwMFx1Yzc3NFx1ZDA2Y1x1YjI5NCBcdWI0NjVcdWFkZjhcdWI3ZjAgXHViYWE4XHVjNTkxXHVjNzQ0IFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzViNFx1YjI5MCBcdWM4MTBcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVjOWMxXHVjMTIwXHVjNzNjXHViODVjIFx1Y2U3Y1x1YzlkMVx1Yzc0NCBcdWIxMjNcdWM1YjQgXHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjIE4gXHVhYzFjXHVjNzU4IFx1Yzg3MFx1YWMwMVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViNGE0LCBcdWFjMDEgXHVjODcwXHVhYzAxXHViOWM4XHViMmU0IDFcdWJkODBcdWQxMzAgTiBcdWFlNGNcdWM5YzAgXHViYzE4XHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWI5ZTRcdWFlMzRcdWIyZTQuIFx1Yzk4OSwmbmJzcDsxIFx1MjI2NiBpIFx1MjI2NiBOXHVjNWQwIFx1YjMwMFx1ZDU3NCwgaSBcdWJjODhcdWM5ZjggXHVjODcwXHVhYzAxXHVjNzQwIGkgLSAxIFx1YmM4OFx1YzlmOFx1YzY0MCBpICsgMSBcdWJjODhcdWM5ZjggXHVjODcwXHVhYzAxXHVhY2ZjIFx1Yzc3OFx1YzgxMVx1ZDU3NFx1Yzc4OFx1YjJlNC4gKFx1YjJlOCwgMFx1YmM4OFx1YzlmOFx1YjI5NCBOIFx1YmM4OFx1YzlmOCwgTiArIDEgXHViYzg4XHVjOWY4XHViMjk0IDFcdWJjODhcdWM5ZjhcdWI4NWMgXHVhYzA0XHVjOGZjXHVkNTVjXHViMmU0KS4gaSBcdWJjODhcdWM5ZjggXHVjODcwXHVhYzAxXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCZuYnNwO0E8c3ViPmk8XC9zdWI+IFx1Yzc3NFx1YzljMFx1YjljYywgXHVjZTdjXHVjOWM4XHVjNzc0IFx1YzExY1x1ZDIzNFx1YjdlYyZuYnNwO0E8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWIyZTRcdWI5NzggXHVhYzEyXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczNcL2Nha2UucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjkwcHg7IHRleHQtYWxpZ246Y2VudGVyOyB3aWR0aDoyOThweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5cdWFkZjhcdWI5YmMgMSA6IFx1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yzc1OCBcdWM2MDgmbmJzcDsoTiA9IDUsIEE8c3ViPjE8XC9zdWI+ID0gMiwgQTxzdWI+MjxcL3N1Yj4gPSA4LCBBPHN1Yj4zPFwvc3ViPiA9IDEsIEE8c3ViPjQ8XC9zdWI+ID0gMTAsIEE8c3ViPjU8XC9zdWI+ID0gOSk8XC9wPlxyXG5cclxuPHA+XHVjNzc0IE5cdWFjMWNcdWI5N2MgSk9JJm5ic3A7XHVhZDcwXHVhY2ZjIElPSSBcdWM1OTFcdWM3NzQgXHViMDk4XHViMjA0XHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC4gXHViMDk4XHViMjA0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YmEzY1x1YzgwMCwgSk9JIFx1YWQ3MFx1Yzc3NCBOIFx1YWMxY1x1Yzc1OCBcdWM4NzBcdWFjMDEgXHVjOTExIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWFjODMgXHVkNTU4XHViMDk4XHViOTdjIFx1YWMwMFx1YzgzOFx1YWMwNFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZGY4IFx1YjRhNCwgSU9JIFx1YzU5MVx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NzQgSU9JIFx1YzU5MVx1YWNmYyBKT0kgXHVhZDcwXHVjNzQwIFx1YmM4OFx1YWMwOFx1YzU0NFx1YWMwMFx1YmE3MCBcdWIwYThcdWM3NDAgXHVjODcwXHVhYzAxXHVjNzQ0IFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWFjMDBcdWM4MzhcdWFjMDRcdWIyZTQuIFx1YjJlOCwgXHVjNzc4XHVjODExXHVkNTVjIFx1Yzg3MFx1YWMwMSBcdWM5MTEgXHVkNTU4XHViMDk4IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWM4NzBcdWFjMDFcdWM3NzQgXHVjNzc0XHViYmY4IFx1YzEyMFx1ZDBkZFx1YjQxYyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWI5Y2MgXHVhYzAwXHVjODM4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMFx1YzgzOFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Yzg3MFx1YWMwMVx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1Yzc4OFx1Yzc0NCBcdWI1NGNcdWM1ZDQsIElPSSBcdWM1OTFcdWM3NDAgXHVhZGY4IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWFjMDBcdWM4MzhcdWFjMDBcdWFjZTAsIEpPSSBcdWFkNzBcdWM3NDAgXHVjNmQwXHVkNTU4XHViMjk0IFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWFjMDBcdWM4MzhcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5KT0kgXHVhZDcwXHVjNzQwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWFjMDBcdWM4MzhcdWM2MjggXHVjODcwXHVhYzAxXHViNGU0IFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDVjXHViMzAwXHVkNjU0XHVkNTU4XHVhY2UwIFx1YzJmNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZjAwXHVjNzc0XHVkMDZjXHVjNzU4IFx1Yzg3MFx1YWMwMSBcdWMyMTggTiBcdWFjZmMsIE4gXHVhYzFjXHVjNzU4IFx1Yzg3MFx1YWMwMVx1Yzc1OCBcdWQwNmNcdWFlMzBcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBKT0kgXHVhZDcwXHVjNzc0IFx1YWMwMFx1YzgzOFx1YzYyYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1Yzg3MFx1YWMwMVx1YjRlNFx1Yzc1OCBcdWQ1NjlcdWFjYzRcdWM3NTggXHVjZDVjXHViMzAwXHVjZTU4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVkNDVjXHVjOTAwXHVjNzg1XHViODI1XHVjNzNjXHViODVjXHViZDgwXHVkMTMwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM3ODVcdWI4MjVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZjAwXHVjNzc0XHVkMDZjXHVhYzAwIE4gXHVhYzFjXHVjNzU4IFx1Yzg3MFx1YWMwMVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyNThcdWM1YjQgXHVjNzg4XHVjNzRjXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1Yzc3NFx1YzViNFx1YzljMFx1YjI5NCBOIFx1YzVmNCBcdWM5MTEgaSBcdWM1ZjQmbmJzcDsoMSBcdTIyNjYgaSBcdTIyNjYgTikgXHVjNWQwXHViMjk0IGkgXHViYzg4XHVjOWY4IFx1Yzg3MFx1YWMwMVx1Yzc1OCBcdWQwNmNcdWFlMzBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0Jm5ic3A7XHVjODE1XHVjMjE4Jm5ic3A7QTxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWM3ODVcdWI4MjUgXHViMzcwXHVjNzc0XHVkMTMwXHViMjk0IFx1YzU0NFx1Yjc5OFx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgXHUyMjY2IE4gXHUyMjY2IDIgMDAwXHVmZjBlPFwvbGk+XHJcblx0PGxpPjEgXHUyMjY2IEE8c3ViPmk8XC9zdWI+Jm5ic3A7XHUyMjY2IDEgMDAwIDAwMCAwMDBcdWZmMGU8XC9saT5cclxuXHQ8bGk+QTxzdWI+aTxcL3N1Yj4gXHViYWE4XHViNDUwIFx1YjJlNFx1Yjk3OCBcdWFjMTJcdWM3NDQgXHVhYzE2XHViMjk0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+Sk9JIFx1YWQ3MFx1Yzc3NCBcdWFjMDBcdWM4MzhcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4NzBcdWFjMDFcdWI0ZTRcdWM3NTggXHVkNTY5XHVhY2M0XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1Y2U1OFx1Yjk3YyBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+Sk9JIFx1YWQ3MFx1Yzc3NCZuYnNwO1x1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjMjFjXHVjMTFjXHViODVjIFx1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yjk3YyBcdWFjMDBcdWM4MzhcdWM2MjRcdWIyOTQgXHVhYzgzXHVjNzc0IFx1Y2Q1Y1x1YzgwMVx1ZDU3NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5KT0kgXHVhZDcwXHVjNzc0IDJcdWJjODhcdWM5ZjggXHVjODcwXHVhYzAxXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YzYyOFx1YjJlNC4gXHVjNzc0IFx1Yzg3MFx1YWMwMVx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgOFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+SU9JIFx1YzU5MVx1Yzc0MCAxXHViYzg4XHVjOWY4IFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWFjMDBcdWM4MzhcdWM2MjhcdWIyZTQuIFx1Yzc3NCBcdWM4NzBcdWFjMDFcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IDJcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPkpPSSBcdWFkNzBcdWM3NzQmbmJzcDs1XHViYzg4XHVjOWY4IFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWFjMDBcdWM4MzhcdWM2MjhcdWIyZTQuIFx1Yzc3NCBcdWM4NzBcdWFjMDFcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IDlcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPklPSSBcdWM1OTFcdWM3NDAgNFx1YmM4OFx1YzlmOCBcdWM4NzBcdWFjMDFcdWM3NDQgXHVhYzAwXHVjODM4XHVjNjI4XHViMmU0LiBcdWM3NzQgXHVjODcwXHVhYzAxXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCAxMFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+Sk9JIFx1YWQ3MFx1Yzc3NCAzXHViYzg4XHVjOWY4IFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWFjMDBcdWM4MzhcdWM2MjhcdWIyZTQuIFx1Yzc3NCBcdWM4NzBcdWFjMDFcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IDFcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjZDVjXHVjODg1XHVjODAxXHVjNzNjXHViODVjLCBKT0kgXHVhZDcwXHVjNzc0IFx1YWMwMFx1YzgzOFx1YzYyOCBcdWM4NzBcdWFjMDFcdWI0ZTQgXHVkMDZjXHVhZTMwXHVjNzU4IFx1ZDU2OVx1YWNjNFx1YjI5NCA4KzkrMSA9IDE4XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwNzE0IiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiXHUzMGIxXHUzMGZjXHUzMGFkXHUzMDZlXHU1MjA3XHUzMDhhXHU1MjA2XHUzMDUxXHVmZjEyIiwiZGVzY3JpcHRpb24iOiI8cD5KT0kgXHUzMDRmXHUzMDkzXHUzMDY4IElPSSBcdTMwNjFcdTMwODNcdTMwOTNcdTMwNmZcdTUzY2NcdTViNTBcdTMwNmVcdTUxNDRcdTU5YjlcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGVKT0kgXHUzMDRmXHUzMDkzXHUzMDZmXHU2NzAwXHU4ZmQxXHUzMDRhXHU4M2QzXHU1YjUwXHU0ZjVjXHUzMDhhXHUzMDZiXHU1MWRkXHUzMDYzXHUzMDY2XHUzMDQ0XHUzMDY2XHVmZjBjXHU0ZWNhXHU2NWU1XHUzMDgyIEpPSSBcdTMwNGZcdTMwOTNcdTMwNmZcdTMwYjFcdTMwZmNcdTMwYWRcdTMwOTJcdTcxM2NcdTMwNDRcdTMwNjZcdTk4ZGZcdTMwNzlcdTMwODhcdTMwNDZcdTMwNjhcdTMwNTdcdTMwNWZcdTMwNmVcdTMwNjBcdTMwNGNcdWZmMGNcdTcxM2NcdTMwNGRcdTMwNDJcdTMwNGNcdTMwNjNcdTMwNWZcdTMwNjhcdTMwNTNcdTMwOGRcdTMwNjdcdTUzMDJcdTMwNDRcdTMwOTJcdTMwNGJcdTMwNGVcdTMwNjRcdTMwNTFcdTMwNWYgSU9JIFx1MzA2MVx1MzA4M1x1MzA5M1x1MzA0Y1x1Njc2NVx1MzA1Zlx1MzA2ZVx1MzA2NyAyXHU0ZWJhXHUzMDY3XHUzMGIxXHUzMGZjXHUzMGFkXHUzMDkyXHU1MjA2XHUzMDUxXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZiXHUzMDZhXHUzMDYzXHUzMDVmXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1MzBiMVx1MzBmY1x1MzBhZFx1MzA2Zlx1NTE4Nlx1NWY2Mlx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZVx1MzA0Mlx1MzA4Ylx1NzBiOVx1MzA0Ylx1MzA4OVx1NjUzZVx1NWMwNFx1NzJiNlx1MzA2Ylx1NTIwN1x1MzA4YVx1NzZlZVx1MzA5Mlx1NTE2NVx1MzA4Y1x1ZmYwY1x1MzBiMVx1MzBmY1x1MzBhZFx1MzA5MiBOIFx1NTAwYlx1MzA2ZVx1MzBkNFx1MzBmY1x1MzBiOVx1MzA2Ylx1NTIwN1x1MzA4YVx1NTIwNlx1MzA1MVx1ZmYwY1x1MzBkNFx1MzBmY1x1MzBiOVx1MzA2YjEgXHUzMDRiXHUzMDg5IE4gXHUzMDdlXHUzMDY3XHU1M2NkXHU2NjQyXHU4YTA4XHU1NmRlXHUzMDhhXHUzMDZiXHU3NTZhXHU1M2Y3XHUzMDkyXHUzMDY0XHUzMDUxXHUzMDVmXHVmZjBlXHUzMDY0XHUzMDdlXHUzMDhhXHVmZjBjMSBcdTIyNjYgaSBcdTIyNjYgTiBcdTMwNmJcdTViZmVcdTMwNTdcdWZmMGNpIFx1NzU2YVx1NzZlZVx1MzA2ZVx1MzBkNFx1MzBmY1x1MzBiOVx1MzA2ZiBpICZtaW51czsgMSBcdTc1NmFcdTc2ZWVcdTMwNjggaSArIDEgXHU3NTZhXHU3NmVlXHUzMDZlXHUzMGQ0XHUzMGZjXHUzMGI5XHUzMDY4XHU5NmEzXHU2M2E1XHUzMDU3XHUzMDY2XHUzMDQ0XHUzMDhiIChcdTMwNWZcdTMwNjBcdTMwNTcgMCBcdTc1NmFcdTc2ZWVcdTMwNmYgTiBcdTc1NmFcdTc2ZWVcdWZmMGNOICsgMSBcdTc1NmFcdTc2ZWVcdTMwNmYgMSBcdTc1NmFcdTc2ZWVcdTMwNjhcdTMwN2ZcdTMwNmFcdTMwNTkpIFx1ZmYwZWkgXHU3NTZhXHU3NmVlXHUzMDZlXHUzMGQ0XHUzMGZjXHUzMGI5XHUzMDZlXHU1OTI3XHUzMDRkXHUzMDU1XHUzMDZmIEE8c3ViPmk8XC9zdWI+IFx1MzA2MFx1MzA2M1x1MzA1Zlx1MzA0Y1x1ZmYwY1x1NTIwN1x1MzA4YVx1NjViOVx1MzA0Y1x1MzA2OFx1MzA2Nlx1MzA4Mlx1NGUwYlx1NjI0Ylx1MzA2MFx1MzA2M1x1MzA1Zlx1MzA2ZVx1MzA2NyBBPHN1Yj5pPFwvc3ViPiBcdTMwNmZcdTMwNTlcdTMwNzlcdTMwNjZcdTc1NzBcdTMwNmFcdTMwOGJcdTUwMjRcdTMwNmJcdTMwNmFcdTMwNjNcdTMwNWZcdWZmMGU8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczNcL2Nha2UucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjkwcHg7IHdpZHRoOjI5OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5cdTU2ZjMgMTogXHUzMGIxXHUzMGZjXHUzMGFkXHUzMDZlXHU0ZjhiIChOID0gNSwgQTEgPSAyLCBBMiA9IDgsIEEzID0gMSwgQTQgPSAxMCwgQTUgPSA5KTxcL3A+XHJcblxyXG48cD5cdTMwNTNcdTMwNmUgTiBcdTUwMGJcdTMwOTIgSk9JIFx1MzA0Zlx1MzA5M1x1MzA2OCBJT0kgXHUzMDYxXHUzMDgzXHUzMDkzXHUzMDY3XHU1MjA2XHUzMDUxXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZiXHUzMDU3XHUzMDVmXHVmZjBlXHU1MjA2XHUzMDUxXHU2NWI5XHUzMDZmXHU2YjIxXHUzMDZlXHUzMDg4XHUzMDQ2XHUzMDZiXHUzMDU5XHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZiXHUzMDU3XHUzMDVmXHVmZjFhPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHUzMDdlXHUzMDVhIEpPSSBcdTMwNGZcdTMwOTNcdTMwNGMgTiBcdTUwMGJcdTMwNmVcdTMwNDZcdTMwNjFcdTMwNmVcdTU5N2RcdTMwNGRcdTMwNmEgMSBcdTMwNjRcdTMwOTJcdTkwNzhcdTMwOTNcdTMwNjdcdTUzZDZcdTMwOGJcdWZmMGU8XC9saT5cclxuXHQ8bGk+XHUzMDVkXHUzMDZlXHU1ZjhjXHVmZjBjSU9JIFx1MzA2MVx1MzA4M1x1MzA5M1x1MzA0Ylx1MzA4OVx1MzA2Zlx1MzA1OFx1MzA4MVx1MzA2NiBJT0kgXHUzMDYxXHUzMDgzXHUzMDkzXHUzMDY4IEpPSSBcdTMwNGZcdTMwOTNcdTMwNGNcdTRlYTRcdTRlOTJcdTMwNmJcdTZiOGJcdTMwOGFcdTMwNmVcdTMwZDRcdTMwZmNcdTMwYjlcdTMwOTIgMSBcdTMwNjRcdTMwNWFcdTMwNjRcdTUzZDZcdTMwNjNcdTMwNjZcdTMwNDRcdTMwNGZcdWZmMGVcdTMwNWZcdTMwNjBcdTMwNTdcdWZmMGNcdTRlMjFcdTk2YTNcdTMwNmVcdTMwZDRcdTMwZmNcdTMwYjlcdTMwNmVcdTMwNDZcdTMwNjFcdTVjMTFcdTMwNmFcdTMwNGZcdTMwNjhcdTMwODJcdTRlMDBcdTY1YjlcdTMwNGNcdTY1ZTJcdTMwNmJcdTUzZDZcdTMwODlcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdTMwODhcdTMwNDZcdTMwNmFcdTMwZDRcdTMwZmNcdTMwYjlcdTMwNTdcdTMwNGJcdTUzZDZcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNGNcdTMwNjdcdTMwNGRcdTMwNWFcdWZmMGNcdTUzZDZcdTMwOGNcdTMwOGJcdTMwZDRcdTMwZmNcdTMwYjlcdTMwNGNcdTg5MDdcdTY1NzBcdTMwNDJcdTMwOGJcdTMwNjhcdTMwNGRcdTMwNmZcdWZmMGNJT0kgXHUzMDYxXHUzMDgzXHUzMDkzXHUzMDZmXHUzMDVkXHUzMDZlXHUzMDQ2XHUzMDYxXHU2NzAwXHUzMDgyXHU1OTI3XHUzMDRkXHUzMDQ0XHUzMDgyXHUzMDZlXHUzMDkyXHU5MDc4XHUzMDkzXHUzMDY3XHU1M2Q2XHUzMDhhXHVmZjBjSk9JIFx1MzA0Zlx1MzA5M1x1MzA2Zlx1MzA1ZFx1MzA2ZVx1MzA0Nlx1MzA2MVx1MzA2N1x1NTk3ZFx1MzA0ZFx1MzA2YVx1MzA4Mlx1MzA2ZVx1MzA5Mlx1OTA3OFx1MzA5M1x1MzA2N1x1NTNkNlx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA0Y1x1MzA2N1x1MzA0ZFx1MzA4Ylx1ZmYwZTxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPkpPSSBcdTMwNGZcdTMwOTNcdTMwNmZcdWZmMGNcdTgxZWFcdTUyMDZcdTMwNGNcdTY3MDBcdTdkNDJcdTc2ODRcdTMwNmJcdTUzZDZcdTMwOGJcdTMwZDRcdTMwZmNcdTMwYjlcdTMwNmVcdTU5MjdcdTMwNGRcdTMwNTVcdTMwNmVcdTU0MDhcdThhMDhcdTMwOTJcdTY3MDBcdTU5MjdcdTUzMTZcdTMwNTdcdTMwNWZcdTMwNDRcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHUzMGIxXHUzMGZjXHUzMGFkXHUzMDZlXHUzMGQ0XHUzMGZjXHUzMGI5XHUzMDZlXHU2NTcwIE4gXHUzMDY4XHVmZjBjTiBcdTUwMGJcdTMwNmVcdTMwZDRcdTMwZmNcdTMwYjlcdTMwNmVcdTU5MjdcdTMwNGRcdTMwNTVcdTMwNmVcdTYwYzVcdTU4MzFcdTMwNGNcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwNWZcdTMwNjhcdTMwNGRcdWZmMGNKT0kgXHUzMDRmXHUzMDkzXHUzMDRjXHU1M2Q2XHUzMDhjXHUzMDhiXHUzMGQ0XHUzMGZjXHUzMGI5XHUzMDZlXHU1OTI3XHUzMDRkXHUzMDU1XHUzMDZlXHU1NDA4XHU4YTA4XHUzMDZlXHU2NzAwXHU1OTI3XHU1MDI0XHUzMDkyXHU2YzQyXHUzMDgxXHUzMDhiXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDkyXHU0ZjVjXHU2MjEwXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdTZhMTlcdTZlOTZcdTUxNjVcdTUyOWJcdTMwNGJcdTMwODlcdTRlZTVcdTRlMGJcdTMwNmVcdTUxNjVcdTUyOWJcdTMwOTJcdThhYWRcdTMwN2ZcdThmYmNcdTMwODFcdWZmMGU8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1NjU3NFx1NjU3MCBOIFx1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0YVx1MzA4YVx1ZmYwY1x1MzBiMVx1MzBmY1x1MzBhZFx1MzA0YyBOIFx1NTAwYlx1MzA2ZVx1MzBkNFx1MzBmY1x1MzBiOVx1MzA2Ylx1NTIwN1x1MzA4YVx1NTIwNlx1MzA1MVx1MzA4OVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5cdTdkOWFcdTMwNGYgTiBcdTg4NGNcdTMwNmVcdTMwNDZcdTMwNjFcdTMwNmUgaSBcdTg4NGNcdTc2ZWUgKDEgXHUyMjY2IGkgXHUyMjY2IE4pIFx1MzA2Ylx1MzA2Zlx1NjU3NFx1NjU3MCBBPHN1Yj5pPFwvc3ViPiBcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNGFcdTMwOGFcdWZmMGNpIFx1NzU2YVx1NzZlZVx1MzA2ZVx1MzBkNFx1MzBmY1x1MzBiOVx1MzA2ZVx1NTkyN1x1MzA0ZFx1MzA1NVx1MzA0YyBBPHN1Yj5pPFwvc3ViPiBcdTMwNjdcdTMwNDJcdTMwOGJcdTMwNTNcdTMwNjhcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGU8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdTMwNTlcdTMwNzlcdTMwNjZcdTMwNmVcdTUxNjVcdTUyOWJcdTMwYzdcdTMwZmNcdTMwYmZcdTMwNmZcdTRlZTVcdTRlMGJcdTMwNmVcdTY3NjFcdTRlZjZcdTMwOTJcdTZlODBcdTMwNWZcdTMwNTlcdWZmMGU8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xIFx1MjI2NiBOIFx1MjI2NiAyIDAwMFx1ZmYwZTxcL2xpPlxyXG5cdDxsaT4xIFx1MjI2NiBBPHN1Yj5pPFwvc3ViPiBcdTIyNjYgMSAwMDAgMDAwIDAwMFx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5BPHN1Yj5pPFwvc3ViPiBcdTMwNmZcdTMwNTlcdTMwNzlcdTMwNjZcdTc1NzBcdTMwNmFcdTMwOGJcdWZmMGU8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1NmExOVx1NmU5Nlx1NTFmYVx1NTI5Ylx1MzA2Ylx1ZmYwY0pPSSBcdTMwNGZcdTMwOTNcdTMwNGNcdTUzZDZcdTMwOGNcdTMwOGJcdTMwZDRcdTMwZmNcdTMwYjlcdTMwNmVcdTU5MjdcdTMwNGRcdTMwNTVcdTMwNmVcdTU0MDhcdThhMDhcdTMwNmVcdTY3MDBcdTU5MjdcdTUwMjRcdTMwOTJcdTg4NjhcdTMwNTlcdTY1NzRcdTY1NzBcdTMwOTIgMSBcdTg4NGNcdTMwNjdcdTUxZmFcdTUyOWJcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJoaW50IjoiPHA+Sk9JIFx1MzA0Zlx1MzA5M1x1MzA2Zlx1ZmYwY1x1NmIyMVx1MzA2ZVx1MzA4OFx1MzA0Nlx1MzA2Ylx1MzBkNFx1MzBmY1x1MzBiOVx1MzA5Mlx1NTNkNlx1MzA4Ylx1MzA2ZVx1MzA0Y1x1NjcwMFx1OTA2OVx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkpPSSBcdTMwNGZcdTMwOTNcdTMwNmYgMiBcdTc1NmFcdTc2ZWVcdTMwNmVcdTMwZDRcdTMwZmNcdTMwYjlcdTMwOTJcdTUzZDZcdTMwOGJcdWZmMGVcdTMwNTNcdTMwNmVcdTMwZDRcdTMwZmNcdTMwYjlcdTMwNmVcdTU5MjdcdTMwNGRcdTMwNTVcdTMwNmYgOCBcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9saT5cclxuXHQ8bGk+SU9JIFx1MzA2MVx1MzA4M1x1MzA5M1x1MzA2ZiAxIFx1NzU2YVx1NzZlZVx1MzA2ZVx1MzBkNFx1MzBmY1x1MzBiOVx1MzA5Mlx1NTNkNlx1MzA4Ylx1ZmYwZVx1MzA1M1x1MzA2ZVx1MzBkNFx1MzBmY1x1MzBiOVx1MzA2ZVx1NTkyN1x1MzA0ZFx1MzA1NVx1MzA2ZiAyIFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5KT0kgXHUzMDRmXHUzMDkzXHUzMDZmIDUgXHU3NTZhXHU3NmVlXHUzMDZlXHUzMGQ0XHUzMGZjXHUzMGI5XHUzMDkyXHU1M2Q2XHUzMDhiXHVmZjBlXHUzMDUzXHUzMDZlXHUzMGQ0XHUzMGZjXHUzMGI5XHUzMDZlXHU1OTI3XHUzMDRkXHUzMDU1XHUzMDZmIDkgXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvbGk+XHJcblx0PGxpPklPSSBcdTMwNjFcdTMwODNcdTMwOTNcdTMwNmYgNCBcdTc1NmFcdTc2ZWVcdTMwNmVcdTMwZDRcdTMwZmNcdTMwYjlcdTMwOTJcdTUzZDZcdTMwOGJcdWZmMGVcdTMwNTNcdTMwNmVcdTMwZDRcdTMwZmNcdTMwYjlcdTMwNmVcdTU5MjdcdTMwNGRcdTMwNTVcdTMwNmYgMTAgXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvbGk+XHJcblx0PGxpPkpPSSBcdTMwNGZcdTMwOTNcdTMwNmYgMyBcdTc1NmFcdTc2ZWVcdTMwNmVcdTMwZDRcdTMwZmNcdTMwYjlcdTMwOTJcdTUzZDZcdTMwOGJcdWZmMGVcdTMwNTNcdTMwNmVcdTMwZDRcdTMwZmNcdTMwYjlcdTMwNmVcdTU5MjdcdTMwNGRcdTMwNTVcdTMwNmYgMSBcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdTY3MDBcdTdkNDJcdTc2ODRcdTMwNmJcdWZmMGNKT0kgXHUzMDRmXHUzMDkzXHUzMDRjXHU1M2Q2XHUzMDYzXHUzMDVmXHUzMGQ0XHUzMGZjXHUzMGI5XHUzMDZlXHU1OTI3XHUzMDRkXHUzMDU1XHUzMDZlXHU1NDA4XHU4YTA4XHUzMDZmXHVmZjBjOCArIDkgKyAxID0gMTggXHUzMDY4XHUzMDZhXHUzMDhiXHVmZjBlPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM3N2NcdWJjZjhcdWM1YjQifV0=

출처

Olympiad > 일본정보올림피아드 > JOI 2015 2번

Baekjoon Online Judge

채점 현황

문제

출처

ACM-ICPC

Coder's High

서버 상태

도움말

© 2018 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 대회 개최 문의
사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 강남대로 359 대우도씨에빛2 5층 502호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: [email protected]
통신판매신고번호: 제 2017-서울서초-2193 호

이 사이트는 ACM 또는 ACM-ICPC 대회와 무관하며, ACM으로부터 승인이나 지원을 받지 않고 있습니다.