시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 173 28 16 27.586%

문제

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

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

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

입력

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

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

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

출력

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

예제 입력 1

4
1 -2 -1 3

예제 출력 1

9
W3sicHJvYmxlbV9pZCI6IjEwMzUwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzQwXHVkNTg5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2ZDRcdWMyYTRcdWQyYjhcdWI5YWNcdWQyYjhcdWM1ZDBcdWIyOTQgblx1YWMxY1x1Yzc1OCBcdWM3NDBcdWQ1ODlcdWM3NzRcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM3NDBcdWQ1ODlcdWM3NDAgXHVjNTkxIFx1YzYwNlx1YzczY1x1Yjg1YyBcdWM3NzRcdWM2YzNcdWQ1NThcdWIyOTQgXHVjNzQwXHVkNTg5XHVjNzc0IFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNzQwXHVkNTg5XHVjNzU4IFx1YzY3Y1x1Y2FiZFx1YzVkMFx1YjI5NCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjNzQwXHVkNTg5XHVjNzc0XHVjNzg4XHVhY2UwLCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3NDBcdWQ1ODlcdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwXHViMjk0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNzQwXHVkNTg5XHVjNzc0XHVjNzg4XHViMmU0KFx1YzZkMFx1ZDYxNVx1YzczY1x1Yjg1YyBcdWIwOThcdWM1ZjRcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQpLiBcdWFjMDEgXHVjNzQwXHVkNTg5XHVjNzQwIEtcdWI5Y2NcdWQwN2NcdWM3NTggXHVjNzkwXHViY2Y4XHVjNzc0IFx1Yzc4OFx1YWNlMCBcdWJhYThcdWI0ZTAgXHVjNzQwXHVkNTg5IFx1Yzc5MFx1YmNmOFx1Yzc1OCBcdWQ1NjlcdWM3NDAgXHVjNTkxXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5pXHViYzg4IFx1Yzc0MFx1ZDU4OVx1Yzc1OCBcdWM3OTBcdWJjZjgsIEsoaSlcdWFjMDAgXHVjNzRjXHVjMjE4XHVjNzdjIFx1YWNiZFx1YzZiMCwgXHVjNzQwXHVkNTg5IFx1YzY5NFx1YzgxNVx1Yzc0MCBcdWM3NzQgXHVjNzkwXHViY2Y4XHVjNzQ0IFx1YzU5MVx1YzIxOFx1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5MDRcdWMyMThcdWM3ODhcdWIyZTQuIFx1YzYwOFx1Yjk3Y1x1YjRlNFx1YzViNCwgXHVjNzkwXHViY2Y4XHVjNzc0IC03XHVjNzdjXHVhY2JkXHVjNmIwLCBcdWM2OTRcdWM4MTVcdWM3NTggXHVkNzk4XHVjNzQ0IFx1YmU0Y1x1YjliMCBcdWQ2YzRcdWM1ZDBcdWIyOTQgXHVjNzkwXHViY2Y4XHVjNzc0IDdcdWM3NzRcdWI0MWNcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjA5OCBcdWM2OTRcdWM4MTVcdWM3NTggXHVkNzk4XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YmE3NCBcdWM3NzRcdWM2YzNcdWQ1NThcdWIyOTQgXHVjNTkxIFx1YzYwNiBcdWM3NDBcdWQ1ODlcdWM3NDAgaVx1Yzc0MFx1ZDU4OSBcdWM3OTBcdWJjZjhcdWM3NTggXHVjODA4XHViMzEzXHVhYzEyXHViOWNjXHVkMDdjIFx1YzE5MFx1ZDU3NFx1Yjk3YyBcdWJjZjhcdWIyZTQuIGlcdWM3NDBcdWQ1ODlcdWM3NTggXHVjNTkxXHVjNjA2IFx1Yzc3NFx1YzZjM1x1Yzc0MFx1ZDU4OVx1Yzc1OCBcdWM3OTBcdWJjZjhcdWM3NzQgNVx1YzY0MCAxMVx1Yzc3NFx1Yjc3Y1x1YmE3NCAtMlx1YzY0MCA0XHViODVjIFx1YzkwNFx1YzViNFx1YjRlMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1Yzc0MFx1ZDU4OVx1Yzc1OCBcdWM3OTBcdWJjZjhcdWM3NDQgMCBcdWI2MTBcdWIyOTQgXHVjNTkxXHVjMjE4XHViODVjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjNjk0XHVjODE1XHVjNzU4IFx1ZDc5OFx1Yzc0NCBcdWJlNGNcdWI4MjRcdWM1N2NcdWQ1NjAgXHVjZDVjXHVjMThjIFx1ZDY5Zlx1YzIxOFx1YjI5NCBcdWM1YmNcdWI5YzhcdWM3N2NcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3NDBcdWQ1ODkgXHVhYzFjXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbHQ7IG4gJmx0OyAxMDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1Yzc0MFx1ZDU4OVx1Yzc1OCBcdWM3OTBcdWJjZjggayhpKVx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoLTMyMDAwICZsdDsgayhpKSAmbHQ7IDMyMDAwKTxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjNzkwXHViY2Y4XHVjNzQwIFx1ZDU1Y1x1Y2U3OFx1Yzc1OCBcdWFjZjVcdWJjMzFcdWM3NDQgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM2OTRcdWM4MTVcdWM3NTggXHVkNzk4XHVjNzQ0IFx1YmU0Y1x1YjgyNFx1YzU3Y1x1ZDU2MCBcdWNkNWNcdWMxOGMgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDM1MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJhbmtzIiwiZGVzY3JpcHRpb24iOiI8cD5PbiBXYWxsIFN0cmVldCBmcm9tIFdvbmRlcmxhbmQsIHdlIGhhdmUgbiBiYW5rcywgd2l0aCAxMDAwMCAmZ3Q7IG4gJmd0OyAwLiBFYWNoIGJhbmsgaGFzIGV4YWN0bHkgdHdvIG5laWdoYm91cnMsIHRoZSBsZWZ0IChMKSBhbmQgcmlnaHQgKFIpIG5laWdoYm91ci4gVGhlIGZpcnN0IGJhbmsmcnNxdW87cyBsZWZ0IG5laWdoYm91ciBpcyB0aGUgbGFzdCBiYW5rLCB3aGlsZSB0aGUgbGFzdCBiYW5rJnJzcXVvO3MgcmlnaHQgbmVpZ2hib3VyIGlzIHRoZSBmaXJzdCBiYW5rLiBFYWNoIGJhbmsgaShuJmd0O2kmZ2U7MCkgaGFzIGEgY2FwaXRhbCBrPHN1Yj5pPFwvc3ViPiB3aXRoIDMyMDAwJmd0O2s8c3ViPmk8XC9zdWI+Jmd0Oy0zMjAwMC4gVGhlIGVudGlyZSBjYXBpdGFsIG9mIGFsbCBiYW5rcyBwdXQgdG9nZXRoZXIgaXMga25vd24gdG8gYmUgcG9zaXRpdmUuIFdoZW5ldmVyIHNvbWUgY2FwaXRhbCBrPHN1Yj5pPFwvc3ViPiBvZiBiYW5rIGkgaXMgbmVnYXRpdmUsIHRoZSBCYW5rIEZhaXJ5IGNhbiBkbyBhIG1hZ2ljIG1vdmUgYW5kIHR1cm4gdGhlIGNhcGl0YWwgaW50byBhIHBvc2l0aXZlIG9uZS4gRm9yIGluc3RhbmNlLCBpZiBrPHN1Yj5pPFwvc3ViPj0tNywgYWZ0ZXIgdGhlIG1hZ2ljIG1vdmUsIGs8c3ViPmk8XC9zdWI+PTcuIFVuZm9ydHVuYXRlbHksIHRoZSBtYWdpYyBtb3ZlIGhhcyBjb25zZXF1ZW5jZXMgZm9yIGJvdGggbmVpZ2hib3VycyBvZiBiYW5rIGkuIEVhY2ggc2VlcyBpdHMgY2FwaXRhbCByZWR1Y2VkIHdpdGggdGhlIGFic29sdXRlIHZhbHVlIG9mIHRoZSBjYXBpdGFsIG9mIGJhbmsgaS4gRm9yIGluc3RhbmNlIGlmIGJhbmsgTCBoYXMgY2FwaXRhbCBrPHN1Yj5MPFwvc3ViPj01IGFuZCBiYW5rIFIgaGFzIGNhcGl0YWwgazxzdWI+UjxcL3N1Yj49MTEsIHRoZW4gYWZ0ZXIgdGhlIG1hZ2ljIG1vdmUgazxzdWI+TDxcL3N1Yj49LTIgYW5kIGs8c3ViPlI8XC9zdWI+PTQuPFwvcD5cclxuXHJcbjxwPldoaWNoIGlzIHRoZSBtaW5pbWFsIG51bWJlciBvZiBtYWdpYyBtb3ZlcyB3aGljaCB0aGUgQmFuayBGYWlyeSBoYXMgdG8gZG8gaW4gb3JkZXIgdG8gbWFrZSB0aGUgY2FwaXRhbCBvZiBhbGwgYmFua3MgZ3JlYXRlciB0aGFuIG9yIGVxdWFsIHRvIDA/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgaW5wdXQgbGluZSwgd2UgaGF2ZSB0aGUgbnVtYmVyIG4gb2YgYmFua3MuIE9uIHRoZSBzZWNvbmQgaW5wdXQgbGluZSwgd2UgaGF2ZSB0aGUgY2FwaXRhbHMgazxzdWI+aTxcL3N1Yj4obiZndDtpJmdlOzApIG9mIGFsbCBiYW5rcywgaW4gdGhlIG9yZGVyIGluIHdoaWNoIHRoZXkgYXJlIGZvdW5kIG9uIFdhbGwgU3RyZWV0IGZyb20gV29uZGVybGFuZC4gRWFjaCBjYXBpdGFsIGlzIHNlcGFyYXRlZCBieSBhIHNpbmdsZSB3aGl0ZXNwYWNlIGZyb20gdGhlIG5leHQgb25lLCBleGNlcHQgZm9yIHRoZSBmaW5hbCBjYXBpdGFsIHdoaWNoIGlzIGRpcmVjdGx5IGZvbGxvd2VkIGJ5IHRoZSBuZXdsaW5lIGNoYXJhY3Rlci48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGNvbnRhaW5zIGEgc2luZ2xlIGxpbmUgd2l0aCB0aGUgdmFsdWUgb2YgdGhlIG1pbmltYWwgbnVtYmVyIG9mIG1hZ2ljIG1vdmVzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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