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

문제

은기는 음이 아닌 정수 n개로 이루어진 수열을 이용해 시간을 때우고 있다. 은기는 수열을 총 k+1개로 나누어야 하고, 각 부분은 비어있지 않아야 한다. 수열을 k+1개로 나누러면, 아래와 같은 과정을 k번 반복해야 한다.

  1. 원소를 두 개 이상 가지고 있는 부분을 고른다. (가장 처음에는 수열 전체밖에 없다)
  2. 임의의 두 원소 사이를 기준으로 수열을 두 부분으로 나눈다.

위의 과정을 할 때마다 얻게되는 점수는 새로 나누어진 각 부분에 들어있는 원소의 합을 곱한 것이다. 위의 과정을 k번 반복하면서 은기가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 n과 k가 주어진다. (2 ≤ n ≤ 100,000, 1 ≤ k ≤ min(n-1, 200)) 둘째 줄에는 수열을 나타내는 음이 아닌 정수 n개 a1, a2, ..., an이 주어진다. (0 ≤ ai ≤ 104)

출력

첫째 줄에 얻을 수 있는 가장 큰 점수를 출력한다. 둘째 줄에는 그러한 점수를 얻기 위해 몇 번째 원소 다음에 수열을 나누어야 하는지 순서대로 출력한다. 가능한 답이 여러개라면, 아무거나 출력한다.

예제 입력 1

7 3
4 1 3 4 0 2 3

예제 출력 1

108
1 3 5

힌트

아래와 같은 과정으로 수열을 나누면 108점을 얻을 수 있다.

  • 현재 수열은 (4, 1, 3, 4, 0, 2, 3)이다. 첫 번째 원소 다음에서 수열을 나누면 4 × (1 + 3 + 4 + 0 + 2 + 3) = 52점을 얻게 된다.
  • 현재 두 부분으로 나누어져 있다. (4), (1, 3, 4, 0, 2, 3) 3번째 원소 다음에서 수열을 나누면 (1 + 3) × (4 + 0 + 2 + 3) = 36점을 얻게 된다.
  • 이제 총 세 부분으로 나누어져 있다. (4), (1, 3), (4, 0, 2, 3) 5번째 원소 다음에서 수열을 나누면 (4 + 0) × (2 + 3) = 20점을 얻게 된다.

수열은 총 4개의 부분 (4), (1, 3), (4, 0), (2, 3) 으로 나누어지게 되고, 은기가 얻은 점수는 52 + 36 + 20 = 108점이다.

W3sicHJvYmxlbV9pZCI6IjEwMDY3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMjE4XHVjNWY0IFx1YjA5OFx1YjIwNFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzQwXHVhZTMwXHViMjk0IFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4IG5cdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YjU0Y1x1YzZiMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc0MFx1YWUzMFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjZDFkIGsrMVx1YWMxY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWFjMDEgXHViZDgwXHViZDg0XHVjNzQwIFx1YmU0NFx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWMyMThcdWM1ZjRcdWM3NDQgaysxXHVhYzFjXHViODVjIFx1YjA5OFx1YjIwNFx1YjdlY1x1YmE3NCwgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3NDQga1x1YmM4OCBcdWJjMThcdWJjZjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YzZkMFx1YzE4Y1x1Yjk3YyBcdWI0NTAgXHVhYzFjIFx1Yzc3NFx1YzBjMSBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YmQ4MFx1YmQ4NFx1Yzc0NCBcdWFjZTBcdWI5NzhcdWIyZTQuIChcdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwXHViMjk0IFx1YzIxOFx1YzVmNCBcdWM4MDRcdWNjYjRcdWJjMTZcdWM1ZDAgXHVjNWM2XHViMmU0KTxcL2xpPlxyXG5cdDxsaT5cdWM3ODRcdWM3NThcdWM3NTggXHViNDUwIFx1YzZkMFx1YzE4YyBcdWMwYWNcdWM3NzRcdWI5N2MgXHVhZTMwXHVjOTAwXHVjNzNjXHViODVjIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWI0NTAgXHViZDgwXHViZDg0XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhY2ZjXHVjODE1XHVjNzQ0IFx1ZDU2MCBcdWI1NGNcdWI5YzhcdWIyZTQgXHVjNWJiXHVhYzhjXHViNDE4XHViMjk0IFx1YzgxMFx1YzIxOFx1YjI5NCBcdWMwYzhcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjOWM0IFx1YWMwMSBcdWJkODBcdWJkODRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzZkMFx1YzE4Y1x1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhY2YxXHVkNTVjIFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNzA0XHVjNzU4IFx1YWNmY1x1YzgxNVx1Yzc0NCBrXHViYzg4IFx1YmMxOFx1YmNmNVx1ZDU1OFx1YmE3NFx1YzExYyBcdWM3NDBcdWFlMzBcdWFjMDAgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODEwXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YzgxNVx1YzIxOCBuXHVhY2ZjIGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IG4gJmxlOyAxMDAsMDAwLCAxICZsZTsgayAmbGU7IG1pbihuLTEsIDIwMCkpIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOCBuXHVhYzFjIGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgLi4uLCBhPHN1Yj5uPFwvc3ViPlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+NDxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZGY4XHViN2VjXHVkNTVjIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWM1YmJcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YmE4NyBcdWJjODhcdWM5ZjggXHVjNmQwXHVjMThjIFx1YjJlNFx1Yzc0Y1x1YzVkMCBcdWMyMThcdWM1ZjRcdWM3NDQgXHViMDk4XHViMjA0XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlY1x1YWMxY1x1Yjc3Y1x1YmE3NCwgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3M2NcdWI4NWMgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YjA5OFx1YjIwNFx1YmE3NCAxMDhcdWM4MTBcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVkNjA0XHVjN2FjIFx1YzIxOFx1YzVmNFx1Yzc0MCAoNCwgMSwgMywgNCwgMCwgMiwgMylcdWM3NzRcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNmQwXHVjMThjIFx1YjJlNFx1Yzc0Y1x1YzVkMFx1YzExYyBcdWMyMThcdWM1ZjRcdWM3NDQgXHViMDk4XHViMjA0XHViYTc0IDQgJnRpbWVzOyAoMSArIDMgKyA0ICsgMCArIDIgKyAzKSA9IDUyXHVjODEwXHVjNzQ0IFx1YzViYlx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1ZDYwNFx1YzdhYyBcdWI0NTAgXHViZDgwXHViZDg0XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuICg0KSwgKDEsIDMsIDQsIDAsIDIsIDMpIDNcdWJjODhcdWM5ZjggXHVjNmQwXHVjMThjIFx1YjJlNFx1Yzc0Y1x1YzVkMFx1YzExYyBcdWMyMThcdWM1ZjRcdWM3NDQgXHViMDk4XHViMjA0XHViYTc0ICgxICsgMykgJnRpbWVzOyAoNCArIDAgKyAyICsgMykgPSAzNlx1YzgxMFx1Yzc0NCBcdWM1YmJcdWFjOGMgXHViNDFjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3NzRcdWM4MWMgXHVjZDFkIFx1YzEzOCBcdWJkODBcdWJkODRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gKDQpLCAoMSwgMyksICg0LCAwLCAyLCAzKSA1XHViYzg4XHVjOWY4IFx1YzZkMFx1YzE4YyBcdWIyZTRcdWM3NGNcdWM1ZDBcdWMxMWMgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YjA5OFx1YjIwNFx1YmE3NCAoNCArIDApICZ0aW1lczsgKDIgKyAzKSA9IDIwXHVjODEwXHVjNzQ0IFx1YzViYlx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjMjE4XHVjNWY0XHVjNzQwIFx1Y2QxZCA0XHVhYzFjXHVjNzU4IFx1YmQ4MFx1YmQ4NCAoNCksICgxLCAzKSwgKDQsIDApLCAoMiwgMykgXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzljMFx1YWM4YyBcdWI0MThcdWFjZTAsIFx1Yzc0MFx1YWUzMFx1YWMwMCBcdWM1YmJcdWM3NDAgXHVjODEwXHVjMjE4XHViMjk0IDUyICsgMzYgKyAyMCA9IDEwOFx1YzgxMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEwMDY3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3BsaXQgdGhlIHNlcXVlbmNlIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIHBsYXlpbmcgYSBnYW1lIHdpdGggYSBzZXF1ZW5jZSBvZiBuIG5vbi1uZWdhdGl2ZSBpbnRlZ2Vycy4gSW4gdGhpcyBnYW1lIHlvdSBoYXZlIHRvIHNwbGl0IHRoZSBzZXF1ZW5jZSBpbnRvIGsgKyAxIG5vbi1lbXB0eSBwYXJ0cy4gVG8gb2J0YWluIGsgKyAxIHBhcnRzIHlvdSByZXBlYXQgdGhlIGZvbGxvd2luZyBzdGVwcyBrIHRpbWVzOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkNob29zZSBhbnkgcGFydCB3aXRoIG1vcmUgdGhhbiBvbmUgZWxlbWVudCAoaW5pdGlhbGx5IHlvdSBoYXZlIG9ubHkgb25lIHBhcnQgJm5kYXNoOyB0aGUgd2hvbGUgc2VxdWVuY2UpLjxcL2xpPlxyXG5cdDxsaT5TcGxpdCBpdCBiZXR3ZWVuIGFueSB0d28gZWxlbWVudHMgdG8gZ2V0IHR3byBuZXcgbm9uLWVtcHR5IHBhcnRzLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPkVhY2ggdGltZSBhZnRlciB0aGVzZSBzdGVwcyB5b3UgZ2FpbiB0aGUgbnVtYmVyIG9mIHBvaW50cyB3aGljaCBpcyBlcXVhbCB0byBwcm9kdWN0IG9mIHN1bXMgb2YgZWxlbWVudHMgb2YgZWFjaCBuZXcgcGFydC4gWW91IHdhbnQgdG8gbWF4aW1pemUgdGhlIHRvdGFsIG51bWJlciBvZiBwb2ludHMgeW91IGdhaW4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSBjb250YWlucyB0d28gaW50ZWdlcnMgbiBhbmQgayAoMiAmbGU7IG4gJmxlOyAxMDAwMDAsIDEgJmxlOyBrICZsZTsgbWluKG4gJm1pbnVzOyAxLCAyMDApKS4gVGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIG4gbm9uLW5lZ2F0aXZlIGludGVnZXJzIGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgLiAuIC4gLCBhPHN1Yj5uPFwvc3ViPiAoMCAmbGU7IGE8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjQ8XC9zdXA+KSAmbmRhc2g7IHRoZSBzZXF1ZW5jZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvdXRwdXQgdGhlIGxhcmdlc3QgdG90YWwgbnVtYmVyIG9mIHBvaW50cyB5b3UgY2FuIGdhaW4uIE9uIHRoZSBzZWNvbmQgbGluZSBvdXRwdXQgayBpbnRlZ2VycyBiZXR3ZWVuIDEgYW5kIG4gJm1pbnVzOyAxICZtZGFzaDsgdGhlIHBvc2l0aW9ucyBvZiBlbGVtZW50cyBhZnRlciB3aGljaCB5b3UgaGF2ZSB0byBzcGxpdCB0aGUgc2VxdWVuY2UgdG8gZ2FpbiB0aGUgbGFyZ2VzdCB0b3RhbCBudW1iZXIgb2YgcG9pbnRzLiBJZiB0aGVyZSBhcmUgbW9yZSB0aGFuIG9uZSB3YXkgdG8gZ2FpbiB0aGUgbGFyZ2VzdCBudW1iZXIgb2YgcG9pbnRzIG91dHB1dCBhbnkgb25lIG9mIHRoZW0uPFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoZSBmaXJzdCBzYW1wbGUgeW91IGNhbiBnYWluIDEwOCBwb2ludHMgYnkgdGhlIGZvbGxvd2luZyB3YXk6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+SW5pdGlhbGx5IHlvdSBoYXZlIHRoZSB3aG9sZSBzZXF1ZW5jZSAoNCwgMSwgMywgNCwgMCwgMiwgMykgYXMgb25lIHBhcnQuIFlvdSB3aWxsIHNwbGl0IHRoZSBzZXF1ZW5jZSBhZnRlciAxc3QgZWxlbWVudCBhbmQgZ2FpbiA0ICZ0aW1lczsgKDEgKyAzICsgNCArIDAgKyAyICsgMykgPSA1MiBwb2ludHMuPFwvbGk+XHJcblx0PGxpPllvdSBoYXZlIHR3byBwYXJ0cyAoNCksICgxLCAzLCA0LCAwLCAyLCAzKS4gWW91IHdpbGwgc3BsaXQgdGhlIHNlcXVlbmNlIGFmdGVyIDNyZCBlbGVtZW50IGFuZCBnYWluICgxICsgMykgJnRpbWVzOyAoNCArIDAgKyAyICsgMykgPSAzNiBwb2ludHMuPFwvbGk+XHJcblx0PGxpPllvdSBoYXZlIHRocmVlIHBhcnRzICg0KSwgKDEsMyksICg0LCAwLCAyLCAzKS4gWW91IHdpbGwgc3BsaXQgdGhlIHNlcXVlbmNlIGFmdGVyIDV0aCBlbGVtZW50IGFuZCBnYWluICg0ICsgMCkgJnRpbWVzOyAoMiArIDMpID0gMjAgcG9pbnRzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlNvLCBhZnRlciB0aGUgc3RlcHMgdGFrZW4gYWJvdmUgeW91IGdldCBmb3VyIHBhcnRzICg0KSwgKDEsMyksICg0LDApLCAoMiwgMykgYW5kIGdhaW4gNTIgKyAzNiArIDIwID0gMTA4IHBvaW50cy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > Asia-Pacific Informatics Olympiad > APIO 2014 2번