시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 920 264 187 28.769%

문제

크기가 N(1≤N≤100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1≤i≤j≤N)에 대한 점수는, (A[i]+…+A[j])×Min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에다가 i부터 j까지의 최소값을 곱한 것이 점수가 된다.

배열이 주어졌을 때, 최대의 점수를 갖는 부분배열을 골라내는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N이 주어진다. 다음 줄에는 A[1], …, A[N]을 나타내는 정수들이 주어진다. 각각의 정수들은 음이 아닌 값을 가지며, 1,000,000을 넘지 않는다.

출력

첫째 줄에 최대 점수를 출력한다.

예제 입력 1

6
3 1 6 4 5 2

예제 출력 1

60

힌트

i=3, j=5일 때, 점수는 (6+4+5)×4=60이 된다.

W3sicHJvYmxlbV9pZCI6IjIxMDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODBcdWJkODRcdWJjMzBcdWM1ZjQgXHVhY2UwXHViOTc0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwNmNcdWFlMzBcdWFjMDAgTigxJmxlO04mbGU7MTAwLDAwMClcdWM3NzggMVx1Y2MyOFx1YzZkMCBcdWJjMzBcdWM1ZjQgQVsxXSwgJmhlbGxpcDssIEFbTl1cdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM1YjRcdWI1YTQgaSwgaigxJmxlO2kmbGU7aiZsZTtOKVx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODEwXHVjMjE4XHViMjk0LCAoQVtpXSsmaGVsbGlwOytBW2pdKSZ0aW1lcztNaW57QVtpXSwgJmhlbGxpcDssIEFbal19XHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVjOTg5LCBpXHViZDgwXHVkMTMwIGpcdWFlNGNcdWM5YzBcdWM3NTggXHVkNTY5XHVjNWQwXHViMmU0XHVhYzAwIGlcdWJkODBcdWQxMzAgalx1YWU0Y1x1YzljMFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhY2YxXHVkNTVjIFx1YWM4M1x1Yzc3NCBcdWM4MTBcdWMyMThcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjMzBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjZDVjXHViMzAwXHVjNzU4IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWFjMTZcdWIyOTQgXHViZDgwXHViZDg0XHViYzMwXHVjNWY0XHVjNzQ0IFx1YWNlOFx1Yjc3Y1x1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgQVsxXSwgJmhlbGxpcDssIEFbTl1cdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOFx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM4MTVcdWMyMThcdWI0ZTRcdWM3NDAgXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWFjMTJcdWM3NDQgXHVhYzAwXHVjOWMwXHViYTcwLCAxLDAwMCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YjMwMCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5pPTMsIGo9NVx1Yzc3YyBcdWI1NGMsIFx1YzgxMFx1YzIxOFx1YjI5NCAoNis0KzUpJnRpbWVzOzQ9NjBcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjEwNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZlZWwgR29vZCIsImRlc2NyaXB0aW9uIjoiPHA+QmlsbCBpcyBkZXZlbG9waW5nIGEgbmV3IG1hdGhlbWF0aWNhbCB0aGVvcnkgZm9yIGh1bWFuIGVtb3Rpb25zLiBIaXMgcmVjZW50IGludmVzdGlnYXRpb25zIGFyZSBkZWRpY2F0ZWQgdG8gc3R1ZHlpbmcgaG93IGdvb2Qgb3IgYmFkIGRheXMgaW5cdWZiMDJ1ZW50IHBlb3BsZSZyc3F1bztzIG1lbW9yaWVzIGFib3V0IHNvbWUgcGVyaW9kIG9mIGxpZmUuPFwvcD5cclxuXHJcbjxwPkEgbmV3IGlkZWEgQmlsbCBoYXMgcmVjZW50bHkgZGV2ZWxvcGVkIGFzc2lnbnMgYSBub24tbmVnYXRpdmUgaW50ZWdlciB2YWx1ZSB0byBlYWNoIGRheSBvZiBodW1hbiBsaWZlLiBCaWxsIGNhbGxzIHRoaXMgdmFsdWUgdGhlIGVtb3Rpb25hbCB2YWx1ZSBvZiB0aGUgZGF5LiBUaGUgZ3JlYXRlciB0aGUgZW1vdGlvbmFsIHZhbHVlIGlzLCB0aGUgYmV0dGVyIHRoZSBkYXkgd2FzLiBCaWxsIHN1Z2dlc3RzIHRoYXQgdGhlIHZhbHVlIG9mIHNvbWUgcGVyaW9kIG9mIGh1bWFuIGxpZmUgaXMgcHJvcG9ydGlvbmFsIHRvIHRoZSBzdW0gb2YgdGhlIGVtb3Rpb25hbCB2YWx1ZXMgb2YgdGhlIGRheXMgaW4gdGhlIGdpdmVuIHBlcmlvZCwgbXVsdGlwbGllZCBieSB0aGUgc21hbGxlc3QgZW1vdGlvbmFsIHZhbHVlIG9mIHRoZSBkYXkgaW4gaXQuIFRoaXMgc2NoZW1hIHJlXHVmYjAyZWN0cyB0aGF0IGdvb2Qgb24gYXZlcmFnZSBwZXJpb2QgY2FuIGJlIGdyZWF0bHkgc3BvaWxlZCBieSBvbmUgdmVyeSBiYWQgZGF5LjxcL3A+XHJcblxyXG48cD5Ob3cgQmlsbCBpcyBwbGFubmluZyB0byBpbnZlc3RpZ2F0ZSBoaXMgb3duIGxpZmUgYW5kIGZpbmQgdGhlIHBlcmlvZCBvZiBoaXMgbGlmZSB0aGF0IGhhZCB0aGUgZ3JlYXRlc3QgdmFsdWUuIEhlbHAgaGltIHRvIGRvIHNvLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29udGFpbnMgbiAmbWRhc2g7IHRoZSBudW1iZXIgb2YgZGF5cyBvZiBCaWxsJnJzcXVvO3MgbGlmZSBoZSBpcyBwbGFubmluZyB0byBpbnZlc3RpZ2F0ZSAoMSAmbGU7IG4gJmxlOyAxMDAgMDAwKS4gVGhlIHJlc3Qgb2YgdGhlIGZpbGUgY29udGFpbnMgbiBpbnRlZ2VyIG51bWJlcnMgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPm48XC9zdWI+IHJhbmdpbmcgZnJvbSAwIHRvIDEwPHN1cD42PFwvc3VwPiAmbWRhc2g7IHRoZSBlbW90aW9uYWwgdmFsdWVzIG9mIHRoZSBkYXlzLiBOdW1iZXJzIGFyZSBzZXBhcmF0ZWQgYnkgc3BhY2VzIGFuZFwvb3IgbGluZSBicmVha3MuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIG91dHB1dCBmaWxlIHByaW50IHRoZSBncmVhdGVzdCB2YWx1ZSBvZiBzb21lIHBlcmlvZCBvZiBCaWxsJnJzcXVvO3MgbGlmZS48XC9wPlxyXG5cclxuPHA+T24gdGhlIHNlY29uZCBsaW5lIHByaW50IHR3byBudW1iZXJzIGwgYW5kIHIgc3VjaCB0aGF0IHRoZSBwZXJpb2QgZnJvbSBsLXRoIHRvIHItdGggZGF5IG9mIEJpbGwmcnNxdW87cyBsaWZlIChpbmNsdXNpdmUpIGhhcyB0aGUgZ3JlYXRlc3QgcG9zc2libGUgdmFsdWUuIElmIHRoZXJlIGFyZSBtdWx0aXBsZSBwZXJpb2RzIHdpdGggdGhlIGdyZWF0ZXN0IHBvc3NpYmxlIHZhbHVlLCB0aGVuIHByaW50IGFueSBvbmUgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=