시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB40717112046.154%

문제

길이가 N인 막대 모양 과자가 있다. 성관이와 도토리는 이 과자를 여러 조각으로 잘라 각자 합이 N/2가 되도록 나눠먹으려 한다. 이 과자는 무엇인지 모를 재료로 만들어졌기 때문에 각 지점마다 자를 때 필요한 힘이 다르다. 알고리즘 캠프를 하느라 너무 지친 성관이는 과자를 자르기 위해 많은 힘을 쓰고 싶지 않다. 과자의 각 위치를 절단하는데 얼마의 힘이 필요한지를 알 때, 두 사람이 과자를 나누기 위해 필요한 최소 힘의 합을 구해주자.

 예를 들어 길이 6인 과자가 있고, 각 지점을 자르는 데 필요한 힘이 왼쪽부터 {1, 8, 12, 6, 2}라면 이때 필요한 최소 힘은 다음과 같이 잘랐을 때의 합인 7이 된다.

입력

첫 줄에 과자의 길이 N(2 ≤ N ≤ 10,000)이 주어진다. 이때 N은 짝수이다. 두 번째 줄부터 N번째 줄까지 맨 왼쪽에서부터 각 지점을 자르는 데 필요한 힘 P(0 ≤ P ≤ 10,000)가 주어진다.

출력

한 줄에 필요한 최소 힘의 합을 출력하라.

예제 입력 1

6
1
8
12
6
2

예제 출력 1

7
W3sicHJvYmxlbV9pZCI6IjU1NjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZmNcdWM3OTBcdWM3NTggXHViZDg0XHVkNTYwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFlMzhcdWM3NzRcdWFjMDAgTlx1Yzc3OCBcdWI5YzlcdWIzMDAgXHViYWE4XHVjNTkxIFx1YWNmY1x1Yzc5MFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YzEzMVx1YWQwMFx1Yzc3NFx1YzY0MCBcdWIzYzRcdWQxYTBcdWI5YWNcdWIyOTQgXHVjNzc0IFx1YWNmY1x1Yzc5MFx1Yjk3YyBcdWM1ZWNcdWI3ZWMgXHVjODcwXHVhYzAxXHVjNzNjXHViODVjIFx1Yzc5OFx1Yjc3YyBcdWFjMDFcdWM3OTAgXHVkNTY5XHVjNzc0IE5cLzJcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1YjA5OFx1YjIyMFx1YmEzOVx1YzczY1x1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWFjZmNcdWM3OTBcdWIyOTQgXHViYjM0XHVjNWM3XHVjNzc4XHVjOWMwIFx1YmFhOFx1Yjk3YyBcdWM3YWNcdWI4Y2NcdWI4NWMgXHViOWNjXHViNGU0XHVjNWI0XHVjODRjXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFjMDEgXHVjOWMwXHVjODEwXHViOWM4XHViMmU0IFx1Yzc5MFx1Yjk3YyBcdWI1NGMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1ZDc5OFx1Yzc3NCBcdWIyZTRcdWI5NzRcdWIyZTQuIFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OCBcdWNlYTBcdWQ1MDRcdWI5N2MgXHVkNTU4XHViMjkwXHViNzdjIFx1YjEwOFx1YmIzNCBcdWM5YzBcdWNlNWMgXHVjMTMxXHVhZDAwXHVjNzc0XHViMjk0IFx1YWNmY1x1Yzc5MFx1Yjk3YyBcdWM3OTBcdWI5NzRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YjljZVx1Yzc0MCBcdWQ3OThcdWM3NDQgXHVjNGYwXHVhY2UwIFx1YzJmNlx1YzljMCBcdWM1NGFcdWIyZTQuIFx1YWNmY1x1Yzc5MFx1Yzc1OCBcdWFjMDEgXHVjNzA0XHVjZTU4XHViOTdjIFx1YzgwOFx1YjJlOFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWM1YmNcdWI5YzhcdWM3NTggXHVkNzk4XHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1Y1x1YzljMFx1Yjk3YyBcdWM1NGMgXHViNTRjLCBcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1YWNmY1x1Yzc5MFx1Yjk3YyBcdWIwOThcdWIyMDRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVkNzk4XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWM4ZmNcdWM3OTAuPFwvcD5cclxuXHJcbjxwPiZuYnNwO1x1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVhZTM4XHVjNzc0IDZcdWM3NzggXHVhY2ZjXHVjNzkwXHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YzljMFx1YzgxMFx1Yzc0NCBcdWM3OTBcdWI5NzRcdWIyOTQgXHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWQ3OThcdWM3NzQgXHVjNjdjXHVjYWJkXHViZDgwXHVkMTMwIHsxLCA4LCAxMiwgNiwgMn1cdWI3N2NcdWJhNzQgXHVjNzc0XHViNTRjIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVkNzk4XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjNzk4XHViNzkwXHVjNzQ0IFx1YjU0Y1x1Yzc1OCBcdWQ1NjlcdWM3NzggN1x1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzU1NjFcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjAzcHg7IHdpZHRoOjMzNnB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YWNmY1x1Yzc5MFx1Yzc1OCBcdWFlMzhcdWM3NzQgTigyICZsZTsgTiAmbGU7IDEwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMgTlx1Yzc0MCBcdWM5ZGRcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIFx1YjllOCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVhYzAxIFx1YzljMFx1YzgxMFx1Yzc0NCBcdWM3OTBcdWI5NzRcdWIyOTQgXHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWQ3OTggUCgwICZsZTsgUCAmbGU7IDEwLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWQ3OThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI1NTYxIiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiXHUzMDRhXHU4M2QzXHU1YjUwXHUzMDZlXHU1MjA2XHU1MjcyIiwiZGVzY3JpcHRpb24iOiI8cD5cdTk1NzdcdTMwNTUgTiBcdTMwZGZcdTMwZWFcdTMwZTFcdTMwZmNcdTMwYzhcdTMwZWJcdTMwNmVcdTY4ZDJcdTcyYjZcdTMwNmVcdTMwNGFcdTgzZDNcdTViNTBcdTMwNGMgMSBcdTY3MmNcdTMwNDJcdTMwOGJcdWZmMDhcdTMwNTNcdTMwNTNcdTMwNjcgTiBcdTMwNmZcdTUwNzZcdTY1NzBcdWZmMDlcdWZmMGUyIFx1NGViYVx1MzA2ZSBKT0lcdTk1YTJcdTRmYzJcdTgwMDVcdTMwNGNcdWZmMGNcdTMwNTNcdTMwNmVcdTMwNGFcdTgzZDNcdTViNTBcdTMwOTJcdTg5MDdcdTY1NzBcdTY3MmNcdTMwNmJcdTUyMDdcdTY1YWRcdTMwNTdcdTMwNjZcdWZmMGNcdTU0MDhcdThhMDggTlwvMlx1MzBkZlx1MzBlYVx1MzBlMVx1MzBmY1x1MzBjOFx1MzBlYlx1MzA1YVx1MzA2NFx1MzA2Ylx1NTIwNlx1MzA1MVx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2Ylx1MzA1N1x1MzA1Zlx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTc0MDZcdTc1MzFcdTMwNmZcdTRlMGRcdTY2MGVcdTMwNjdcdTMwNDJcdTMwOGJcdTMwNGNcdWZmMGNcdTMwNTNcdTMwNmVcdTMwNGFcdTgzZDNcdTViNTBcdTMwNmZcdTU4MzRcdTYyNDBcdTMwNmJcdTMwODhcdTMwNjNcdTMwNjZcdTUyMDdcdTY1YWRcdTMwNmVcdTMwNTdcdTMwODRcdTMwNTlcdTMwNTVcdTMwNGNcdTc1NzBcdTMwNmFcdTMwNjNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGUyIFx1NGViYVx1MzA2Zlx1ZmYwY1x1MzA0YVx1ODNkM1x1NWI1MFx1MzA5Mlx1NWRlNlx1MzA0Ylx1MzA4OSAxIFx1MzBkZlx1MzBlYVx1MzBlMVx1MzBmY1x1MzBjOFx1MzBlYlx1MzA1NFx1MzA2OFx1MzA2Ylx1OGFiZlx1MzA3OVx1ZmYwY1x1NTQwNFx1NTgzNFx1NjI0MFx1MzA2N1x1NTIwN1x1NjVhZFx1MzA2Ylx1NGY1NVx1NzlkMlx1MzA0Ylx1MzA0Ylx1MzA4Ylx1MzA0Ylx1MzA5Mlx1NTI3Mlx1MzA4YVx1NTFmYVx1MzA1N1x1MzA1Zlx1ZmYwZTIgXHU0ZWJhXHUzMDRjXHUzMDRhXHU4M2QzXHU1YjUwXHUzMDkyXHU1MjA2XHUzMDUxXHUzMDhiXHUzMDVmXHUzMDgxXHUzMDZlXHU1MjA3XHU2NWFkXHUzMDZiXHUzMDRiXHUzMDRiXHUzMDhiXHU3OWQyXHU2NTcwXHUzMDZlXHU2NzAwXHU1YzBmXHU1MDI0XHUzMDkyXHU2YzQyXHUzMDgxXHUzMDhiXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDkyXHU0ZjVjXHU2MjEwXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdTUxNjVcdTUyOWJcdTMwNmUgMSBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdWZmMGNcdTY4ZDJcdTMwNmVcdTk1NzdcdTMwNTUgTigyICZsZTsgTiAmbGU7IDEwMDAwIFx1ZmYwY1x1MzA1Zlx1MzA2MFx1MzA1NyBOIFx1MzA2Zlx1NTA3Nlx1NjU3MCkgXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHU1MTY1XHU1MjliXHUzMDZlIGkgKyAxIFx1ODg0Y1x1NzZlZSAoMSAmbGU7IGkgJmxlOyBOICZtaW51czsgMSkgXHUzMDZiXHUzMDZmXHVmZjBjXHU1ZGU2XHU3YWVmXHUzMDRiXHUzMDg5IGkgXHUzMGRmXHUzMGVhXHUzMGUxXHUzMGZjXHUzMGM4XHUzMGViXHU3NmVlXHUzMDZlXHU1ODM0XHU2MjQwXHUzMDZlXHU1MjA3XHU2NWFkXHUzMDZiXHUzMDRiXHUzMDRiXHUzMDhiXHU3OWQyXHU2NTcwXHUzMDkyXHU4ODY4XHUzMDU5XHU2NTc0XHU2NTcwIHQ8c3ViPmk8XC9zdWI+ICgxICZsZTsgdDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAwMCkgXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHU1MjA3XHU2NWFkXHU1M2VmXHU4MGZkXHUzMDZhXHU1ODM0XHU2MjQwXHUzMDRjTiAmbWludXM7IDEgXHU3Yjg3XHU2MjQwXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZiXHU2Y2U4XHU2MTBmXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+MiBcdTRlYmFcdTMwNGNcdTMwNGFcdTgzZDNcdTViNTBcdTMwOTJcdTUyMDZcdTMwOGJcdTMwNWZcdTMwODFcdTMwNmVcdTUyMDdcdTY1YWRcdTMwNmJcdTMwNGJcdTMwNGJcdTMwOGJcdTc5ZDJcdTY1NzBcdTMwNmVcdTY3MDBcdTVjMGZcdTUwMjRcdTMwOTJcdTU0MmJcdTMwODAgMSBcdTg4NGNcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdWZmMGU8XC9wPlxyXG4iLCJoaW50IjoiPHA+XHUzMDUzXHUzMDZlXHU1ODM0XHU1NDA4XHVmZjBjXHU1ZGU2XHU3YWVmXHUzMDRiXHUzMDg5IDEgXHUzMGRmXHUzMGVhXHUzMGUxXHUzMGZjXHUzMGM4XHUzMGViXHUzMDY4IDQgXHUzMGRmXHUzMGVhXHUzMGUxXHUzMGZjXHUzMGM4XHUzMGViXHUzMDZlXHU1ODM0XHU2MjQwXHUzMDY3XHU1MjA3XHU2NWFkXHUzMDU5XHUzMDhiXHUzMDY4XHUzMDRiXHUzMDRiXHUzMDhiIFx1NzlkMlx1NjU3MFx1MzA0Y1x1NjcwMFx1NWMwZlx1MzA2OFx1MzA2YVx1MzA4Ylx1ZmYwZVx1MzA0Ylx1MzA0Ylx1MzA4Ylx1NzlkMlx1NjU3MFx1MzA2ZiAxIFx1NzlkMlx1MzA2OCA2IFx1NzlkMlx1MzA2N1x1ZmYwY1x1NTQwOFx1OGEwOCA3IFx1NzlkMlx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzA1NzdlMTI2LWM5N2YtNGE3OS1iNDc4LTRlNGY0NDJkOGMxZFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMzA3cHg7IGhlaWdodDogMjI4cHg7XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJKYXBhbmVzZSJ9XQ==

출처

Olympiad > Japanese Olympiad in Informatics > JOI 2009/2010 2번

  • 문제를 번역한 사람: Acka
  • 문제의 오타를 찾은 사람: anjupiter