시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB90522542190328.764%

문제

크기가 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이 된다.

W3sicHJvYmxlbV9pZCI6IjIxMDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODBcdWJkODRcdWJjMzBcdWM1ZjQgXHVhY2UwXHViOTc0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwNmNcdWFlMzBcdWFjMDAgTigxICZsZTsgTiAmbGU7IDEwMCwwMDApXHVjNzc4IDFcdWNjMjhcdWM2ZDAgXHViYzMwXHVjNWY0IEFbMV0sICZoZWxsaXA7LCBBW05dXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNWI0XHViNWE0IGksIGooMSAmbGU7IGkgJmxlOyBqICZsZTsgTilcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxMFx1YzIxOFx1YjI5NCwgKEFbaV0gKyAmaGVsbGlwOyArIEFbal0pICZ0aW1lczsgbWlue0FbaV0sICZoZWxsaXA7LCBBW2pdfVx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1Yzk4OSwgaVx1YmQ4MFx1ZDEzMCBqXHVhZTRjXHVjOWMwXHVjNzU4IFx1ZDU2OVx1YzVkMCZuYnNwO2lcdWJkODBcdWQxMzAgalx1YWU0Y1x1YzljMFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhY2YxXHVkNTVjIFx1YWM4M1x1Yzc3NCBcdWM4MTBcdWMyMThcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjMzBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjZDVjXHViMzAwXHVjNzU4IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWFjMTZcdWIyOTQgXHViZDgwXHViZDg0XHViYzMwXHVjNWY0XHVjNzQ0IFx1YWNlOFx1Yjc3Y1x1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgQVsxXSwgJmhlbGxpcDssIEFbTl1cdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOFx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM4MTVcdWMyMThcdWI0ZTRcdWM3NDAgXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWFjMTJcdWM3NDQgXHVhYzAwXHVjOWMwXHViYTcwLCAxLDAwMCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YjMwMCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5pID0gMywgaiA9IDVcdWM3N2MgXHViNTRjLCBcdWM4MTBcdWMyMThcdWIyOTQgKDYgKyA0ICsgNSkgJnRpbWVzOyA0ID0gNjBcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjEwNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZlZWwgR29vZCIsImRlc2NyaXB0aW9uIjoiPHA+QmlsbCBpcyBkZXZlbG9waW5nIGEgbmV3IG1hdGhlbWF0aWNhbCB0aGVvcnkgZm9yIGh1bWFuIGVtb3Rpb25zLiBIaXMgcmVjZW50IGludmVzdGlnYXRpb25zIGFyZSBkZWRpY2F0ZWQgdG8gc3R1ZHlpbmcgaG93IGdvb2Qgb3IgYmFkIGRheXMgaW5cdWZiMDJ1ZW50IHBlb3BsZSZyc3F1bztzIG1lbW9yaWVzIGFib3V0IHNvbWUgcGVyaW9kIG9mIGxpZmUuPFwvcD5cclxuXHJcbjxwPkEgbmV3IGlkZWEgQmlsbCBoYXMgcmVjZW50bHkgZGV2ZWxvcGVkIGFzc2lnbnMgYSBub24tbmVnYXRpdmUgaW50ZWdlciB2YWx1ZSB0byBlYWNoIGRheSBvZiBodW1hbiBsaWZlLiBCaWxsIGNhbGxzIHRoaXMgdmFsdWUgdGhlIGVtb3Rpb25hbCB2YWx1ZSBvZiB0aGUgZGF5LiBUaGUgZ3JlYXRlciB0aGUgZW1vdGlvbmFsIHZhbHVlIGlzLCB0aGUgYmV0dGVyIHRoZSBkYXkgd2FzLiBCaWxsIHN1Z2dlc3RzIHRoYXQgdGhlIHZhbHVlIG9mIHNvbWUgcGVyaW9kIG9mIGh1bWFuIGxpZmUgaXMgcHJvcG9ydGlvbmFsIHRvIHRoZSBzdW0gb2YgdGhlIGVtb3Rpb25hbCB2YWx1ZXMgb2YgdGhlIGRheXMgaW4gdGhlIGdpdmVuIHBlcmlvZCwgbXVsdGlwbGllZCBieSB0aGUgc21hbGxlc3QgZW1vdGlvbmFsIHZhbHVlIG9mIHRoZSBkYXkgaW4gaXQuIFRoaXMgc2NoZW1hIHJlXHVmYjAyZWN0cyB0aGF0IGdvb2Qgb24gYXZlcmFnZSBwZXJpb2QgY2FuIGJlIGdyZWF0bHkgc3BvaWxlZCBieSBvbmUgdmVyeSBiYWQgZGF5LjxcL3A+XHJcblxyXG48cD5Ob3cgQmlsbCBpcyBwbGFubmluZyB0byBpbnZlc3RpZ2F0ZSBoaXMgb3duIGxpZmUgYW5kIGZpbmQgdGhlIHBlcmlvZCBvZiBoaXMgbGlmZSB0aGF0IGhhZCB0aGUgZ3JlYXRlc3QgdmFsdWUuIEhlbHAgaGltIHRvIGRvIHNvLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29udGFpbnMgbiAmbWRhc2g7IHRoZSBudW1iZXIgb2YgZGF5cyBvZiBCaWxsJnJzcXVvO3MgbGlmZSBoZSBpcyBwbGFubmluZyB0byBpbnZlc3RpZ2F0ZSAoMSAmbGU7IG4gJmxlOyAxMDAgMDAwKS4gVGhlIHJlc3Qgb2YgdGhlIGZpbGUgY29udGFpbnMgbiBpbnRlZ2VyIG51bWJlcnMgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPm48XC9zdWI+IHJhbmdpbmcgZnJvbSAwIHRvIDEwPHN1cD42PFwvc3VwPiAmbWRhc2g7IHRoZSBlbW90aW9uYWwgdmFsdWVzIG9mIHRoZSBkYXlzLiBOdW1iZXJzIGFyZSBzZXBhcmF0ZWQgYnkgc3BhY2VzIGFuZFwvb3IgbGluZSBicmVha3MuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIG91dHB1dCBmaWxlIHByaW50IHRoZSBncmVhdGVzdCB2YWx1ZSBvZiBzb21lIHBlcmlvZCBvZiBCaWxsJnJzcXVvO3MgbGlmZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d