시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 270 59 29 24.167%

문제

월 스트리트에는 n개의 은행이 있다. 모든 은행은 양 옆으로 이웃하는 은행이 하나씩 있으며, 첫 번째 은행의 왼쪽에는 마지막 은행이 있고, 마지막 은행의 오른쪽에는 첫 번째 은행이 있다(즉, 은행은 원형으로 나열되어있다). 각 은행은 Ki만큼의 자본이 있고 모든 은행 자본의 합은 양수이다.

i번 은행의 자본, Ki가 음수일 경우, 은행 요정은 이 자본을 양수로 만들어 줄 수있다. 예를 들어, 자본이 -7일 경우, 요정의 힘을 빌린 후에는 자본이 7이 된다. 그러나 요정의 힘을 사용하면 이웃하는 양 옆 은행은 i번 은행 자본의 절댓값만큼 손해를 본다. i번 은행의 양옆 이웃 은행의 자본이 5와 11이라면 -2와 4로 줄어든다.

모든 은행의 자본을 0 또는 양수로 만들기 위해 요정의 힘을 빌려야 할 최소 횟수는 얼마일까?

입력

첫 번째 줄에는 은행 개수 n이 주어진다. (0 < n < 10000)

두 번째 줄에는 각 은행의 자본 Ki가 순서대로 주어진다. (-32000 < Ki < 32000)

각 자본은 한 칸의 공백을 두고 주어진다.

출력

요정의 힘을 빌려야 할 최소 횟수를 출력한다.

예제 입력 1

4
1 -2 -1 3

예제 출력 1

9
W3sicHJvYmxlbV9pZCI6IjEwMzUwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzQwXHVkNTg5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2ZDQgXHVjMmE0XHVkMmI4XHViOWFjXHVkMmI4XHVjNWQwXHViMjk0IG5cdWFjMWNcdWM3NTggXHVjNzQwXHVkNTg5XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1Yzc0MFx1ZDU4OVx1Yzc0MCBcdWM1OTEgXHVjNjA2XHVjNzNjXHViODVjIFx1Yzc3NFx1YzZjM1x1ZDU1OFx1YjI5NCBcdWM3NDBcdWQ1ODlcdWM3NzQgXHVkNTU4XHViMDk4XHVjNTI5IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM3NDBcdWQ1ODlcdWM3NTggXHVjNjdjXHVjYWJkXHVjNWQwXHViMjk0IFx1YjljOFx1YzljMFx1YjljOSBcdWM3NDBcdWQ1ODlcdWM3NzQgXHVjNzg4XHVhY2UwLCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjNzQwXHVkNTg5XHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzc0MFx1ZDU4OVx1Yzc3NCBcdWM3ODhcdWIyZTQoXHVjOTg5LCBcdWM3NDBcdWQ1ODlcdWM3NDAmbmJzcDtcdWM2ZDBcdWQ2MTVcdWM3M2NcdWI4NWMgXHViMDk4XHVjNWY0XHViNDE4XHVjNWI0XHVjNzg4XHViMmU0KS4gXHVhYzAxIFx1Yzc0MFx1ZDU4OVx1Yzc0MCBLPHN1Yj5pPFwvc3ViPlx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWM3OTBcdWJjZjhcdWM3NzQgXHVjNzg4XHVhY2UwIFx1YmFhOFx1YjRlMCBcdWM3NDBcdWQ1ODkgXHVjNzkwXHViY2Y4XHVjNzU4IFx1ZDU2OVx1Yzc0MCBcdWM1OTFcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmlcdWJjODggXHVjNzQwXHVkNTg5XHVjNzU4IFx1Yzc5MFx1YmNmOCwgSzxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjNzRjXHVjMjE4XHVjNzdjIFx1YWNiZFx1YzZiMCwgXHVjNzQwXHVkNTg5IFx1YzY5NFx1YzgxNVx1Yzc0MCBcdWM3NzQgXHVjNzkwXHViY2Y4XHVjNzQ0IFx1YzU5MVx1YzIxOFx1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YjQgXHVjOTA0IFx1YzIxOFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNzkwXHViY2Y4XHVjNzc0IC03XHVjNzdjIFx1YWNiZFx1YzZiMCwgXHVjNjk0XHVjODE1XHVjNzU4IFx1ZDc5OFx1Yzc0NCBcdWJlNGNcdWI5YjAgXHVkNmM0XHVjNWQwXHViMjk0IFx1Yzc5MFx1YmNmOFx1Yzc3NCA3XHVjNzc0IFx1YjQxY1x1YjJlNC4gXHVhZGY4XHViN2VjXHViMDk4IFx1YzY5NFx1YzgxNVx1Yzc1OCBcdWQ3OThcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTU4XHViYTc0IFx1Yzc3NFx1YzZjM1x1ZDU1OFx1YjI5NCBcdWM1OTEgXHVjNjA2IFx1Yzc0MFx1ZDU4OVx1Yzc0MCBpXHViYzg4IFx1Yzc0MFx1ZDU4OSBcdWM3OTBcdWJjZjhcdWM3NTggXHVjODA4XHViMzEzXHVhYzEyXHViOWNjXHVkMDdjIFx1YzE5MFx1ZDU3NFx1Yjk3YyBcdWJjZjhcdWIyZTQuIGlcdWJjODggXHVjNzQwXHVkNTg5XHVjNzU4IFx1YzU5MVx1YzYwNiBcdWM3NzRcdWM2YzMgXHVjNzQwXHVkNTg5XHVjNzU4IFx1Yzc5MFx1YmNmOFx1Yzc3NCA1XHVjNjQwIDExXHVjNzc0XHViNzdjXHViYTc0IC0yXHVjNjQwIDRcdWI4NWMgXHVjOTA0XHVjNWI0XHViNGUwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjNzQwXHVkNTg5XHVjNzU4IFx1Yzc5MFx1YmNmOFx1Yzc0NCAwIFx1YjYxMFx1YjI5NCBcdWM1OTFcdWMyMThcdWI4NWMgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM2OTRcdWM4MTVcdWM3NTggXHVkNzk4XHVjNzQ0IFx1YmU0Y1x1YjgyNFx1YzU3YyBcdWQ1NjAgXHVjZDVjXHVjMThjIFx1ZDY5Zlx1YzIxOFx1YjI5NCBcdWM1YmNcdWI5YzhcdWM3N2NcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3NDBcdWQ1ODkgXHVhYzFjXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbHQ7IG4gJmx0OyAxMDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1Yzc0MFx1ZDU4OVx1Yzc1OCBcdWM3OTBcdWJjZjggSzxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKC0zMjAwMCAmbHQ7IEs8c3ViPmk8XC9zdWI+ICZsdDsgMzIwMDApPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWM3OTBcdWJjZjhcdWM3NDAgXHVkNTVjIFx1Y2U3OFx1Yzc1OCBcdWFjZjVcdWJjMzFcdWM3NDQgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM2OTRcdWM4MTVcdWM3NTggXHVkNzk4XHVjNzQ0IFx1YmU0Y1x1YjgyNFx1YzU3YyBcdWQ1NjAgXHVjZDVjXHVjMThjIFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPGEgaWQ9XCJjb21tZW50LTg4Nzg5XCI+PFwvYT48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMDM1MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJhbmtzIiwiZGVzY3JpcHRpb24iOiI8cD5PbiBXYWxsIFN0cmVldCBmcm9tIFdvbmRlcmxhbmQsIHdlIGhhdmUgbiBiYW5rcywgd2l0aCAxMDAwMCAmZ3Q7IG4gJmd0OyAwLiBFYWNoIGJhbmsgaGFzIGV4YWN0bHkgdHdvIG5laWdoYm91cnMsIHRoZSBsZWZ0IChMKSBhbmQgcmlnaHQgKFIpIG5laWdoYm91ci4gVGhlIGZpcnN0IGJhbmsmcnNxdW87cyBsZWZ0IG5laWdoYm91ciBpcyB0aGUgbGFzdCBiYW5rLCB3aGlsZSB0aGUgbGFzdCBiYW5rJnJzcXVvO3MgcmlnaHQgbmVpZ2hib3VyIGlzIHRoZSBmaXJzdCBiYW5rLiBFYWNoIGJhbmsgaShuJmd0O2kmZ2U7MCkgaGFzIGEgY2FwaXRhbCBrPHN1Yj5pPFwvc3ViPiB3aXRoIDMyMDAwJmd0O2s8c3ViPmk8XC9zdWI+Jmd0Oy0zMjAwMC4gVGhlIGVudGlyZSBjYXBpdGFsIG9mIGFsbCBiYW5rcyBwdXQgdG9nZXRoZXIgaXMga25vd24gdG8gYmUgcG9zaXRpdmUuIFdoZW5ldmVyIHNvbWUgY2FwaXRhbCBrPHN1Yj5pPFwvc3ViPiBvZiBiYW5rIGkgaXMgbmVnYXRpdmUsIHRoZSBCYW5rIEZhaXJ5IGNhbiBkbyBhIG1hZ2ljIG1vdmUgYW5kIHR1cm4gdGhlIGNhcGl0YWwgaW50byBhIHBvc2l0aXZlIG9uZS4gRm9yIGluc3RhbmNlLCBpZiBrPHN1Yj5pPFwvc3ViPj0tNywgYWZ0ZXIgdGhlIG1hZ2ljIG1vdmUsIGs8c3ViPmk8XC9zdWI+PTcuIFVuZm9ydHVuYXRlbHksIHRoZSBtYWdpYyBtb3ZlIGhhcyBjb25zZXF1ZW5jZXMgZm9yIGJvdGggbmVpZ2hib3VycyBvZiBiYW5rIGkuIEVhY2ggc2VlcyBpdHMgY2FwaXRhbCByZWR1Y2VkIHdpdGggdGhlIGFic29sdXRlIHZhbHVlIG9mIHRoZSBjYXBpdGFsIG9mIGJhbmsgaS4gRm9yIGluc3RhbmNlIGlmIGJhbmsgTCBoYXMgY2FwaXRhbCBrPHN1Yj5MPFwvc3ViPj01IGFuZCBiYW5rIFIgaGFzIGNhcGl0YWwgazxzdWI+UjxcL3N1Yj49MTEsIHRoZW4gYWZ0ZXIgdGhlIG1hZ2ljIG1vdmUgazxzdWI+TDxcL3N1Yj49LTIgYW5kIGs8c3ViPlI8XC9zdWI+PTQuPFwvcD5cclxuXHJcbjxwPldoaWNoIGlzIHRoZSBtaW5pbWFsIG51bWJlciBvZiBtYWdpYyBtb3ZlcyB3aGljaCB0aGUgQmFuayBGYWlyeSBoYXMgdG8gZG8gaW4gb3JkZXIgdG8gbWFrZSB0aGUgY2FwaXRhbCBvZiBhbGwgYmFua3MgZ3JlYXRlciB0aGFuIG9yIGVxdWFsIHRvIDA/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgaW5wdXQgbGluZSwgd2UgaGF2ZSB0aGUgbnVtYmVyIG4gb2YgYmFua3MuIE9uIHRoZSBzZWNvbmQgaW5wdXQgbGluZSwgd2UgaGF2ZSB0aGUgY2FwaXRhbHMgazxzdWI+aTxcL3N1Yj4obiZndDtpJmdlOzApIG9mIGFsbCBiYW5rcywgaW4gdGhlIG9yZGVyIGluIHdoaWNoIHRoZXkgYXJlIGZvdW5kIG9uIFdhbGwgU3RyZWV0IGZyb20gV29uZGVybGFuZC4gRWFjaCBjYXBpdGFsIGlzIHNlcGFyYXRlZCBieSBhIHNpbmdsZSB3aGl0ZXNwYWNlIGZyb20gdGhlIG5leHQgb25lLCBleGNlcHQgZm9yIHRoZSBmaW5hbCBjYXBpdGFsIHdoaWNoIGlzIGRpcmVjdGx5IGZvbGxvd2VkIGJ5IHRoZSBuZXdsaW5lIGNoYXJhY3Rlci48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGNvbnRhaW5zIGEgc2luZ2xlIGxpbmUgd2l0aCB0aGUgdmFsdWUgb2YgdGhlIG1pbmltYWwgbnVtYmVyIG9mIG1hZ2ljIG1vdmVzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2014 A번