문제
n개의 자연수로 이루어진 수열이 있다.
이 수열을 입력된 순서를 유지한 채로 k+1개의 부분수열로 나눈다.
k+1개의 수열을 얻기 위하여 아래의 방법을 k번 반복한다.
2개 이상의 원소를 가진 임의의 부분 수열을 선택한다. (처음 선택하는 수열은 주어진 수열 전체가 된다.)
선택한 부분 수열에 있는 임의의 어느 두 원소 사이를 나누어 두 개의 그룹으로 나눈다.
위와 같은 단계를 거친 후 점수를 얻게 되는데 그 점수는 각 단계에서 나누어진 두 부분수열의 합을 구하여 곱한 것을 모두 합한 것이 된다.
얻게 되는 점수의 최대값을 구하는 프로그램을 작성하시오.
입력
첫 행에 두 정수 n(2 ≤ n ≤ 100,000)과 k( 1≤ k ≤ min(n-1, 200))이 입력된다.
두 번째 행에 n개의 음이 아닌 정수 ai(0 ≤ ai ≤ 10,000)가 공백으로 구분하여 입력된다.
출력
첫 행에 얻을 수 있는 최대 점수를 출력한다.
두 번째 행에 최대점수를 얻게 하는 원소의 위치를 작업한 순서대로 출력한다.
답이 여러 가지가 나오는 경우 그 중 한 가지만 출력한다.
예제
7 3
4 1 3 4 0 2 3
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), (1,3), (4,0), (2, 3)로 네 그룹이 되며 52 + 36 + 20 = 108점을 얻게 된다.
로그인해야 코드를 작성할 수 있어요.