시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 128 MB 46 10 (22%) 9
문제
시간 제한 2초, 메모리 제한 128MB 당신은 $n$개의 음이 아닌 정수로 이루어진 수열을 사용하는 게임을 하게 된다. 이 게임에서 당신은 수열을 $k+1$개의 부분(아무것도 없는 부분은 허용하지 않음)으로 나눠야 한다. $k+1$개의 부분을 얻기 위해서 다음과 같은 과정을 $k$번 적용해야 한다. ``` 1. 한 개 이상의 값을 가지고 있는 부분을 고른다(처음에는 전체 수열인 하나의 부분만 존재.) 2. 어떤 두 값의 사이를 잘라서 두 개의 부분(각 부분은 한 개 이상의 값을 가지게 됨)으로 나눈다. ``` 이러한 과정을 적용할 때마다 새로 생기는 두 개의 부분에서 각자 가진 값들의 합을 곱한 만큼 점수를 얻게 된다. 이러한 점수의 합을 최대화하는 방법을 구하라.
입력
첫째 줄에 두 개의 정수 $n, k (k + 1 ≤ n)$이 주어진다. 둘째 줄에는 음이 아닌 $n$개의 정수 $a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^4)$로 수열이 주어진다.
출력
첫째 줄에 얻을 수 있는 최고 점수를 출력하라. 둘때 줄에는 $1$에서 $n-1$사이의 정수 $k$개를 출력하는데 이는 이 최고 점수를 얻기 위해서 수열을 자른 위치를 의미한다. 답을 구하는 방법이 한 가지 이상이라면 그 중 아무 경우나 출력해도 된다.
힌트
#### 예제 입력 ``` 7 3 4 1 3 4 0 2 3 ``` #### 예제 출력 ``` 108 1 3 5 ``` #### 참고 첫째 예제에서 다음과 같이 한다면 108점을 얻을 수 있다. ``` 처음엔 전체 수열 (4, 1, 3, 4, 0, 2, 3)이 있다. 여기서 첫째 값의 뒤를 자르면 4 x (1 + 3 + 4 + 0 + 2 + 3) = 52점을 얻을 수 있다. 이제 두 개의 부분 (4), (1, 3, 4, 0, 2, 3)이 있다. 여기서 세번째 값의 뒤를 자르면 (1 + 3) x (4 + 0 + 2 + 3) = 36점을 얻게 된다. 이제 세 개의 부분 (4), (1, 3), (4, 0, 2, 3)이 있다. 여기서 다섯번째 값의 뒤를 자르면 (4 + 0) x (2 + 3) = 20점을 얻게 된다. ``` #### 점수 아래 6개의 서브태스크로 점수가 매겨진다. - 서브태스크 1 (11점) : $1 ≤ k < n ≤ 10$ - 서브태스크 2 (11점) : $1 ≤ k < n ≤ 50$ - 서브태스크 3 (11점) : $1 ≤ k < n ≤ 200$ - 서브태스크 4 (17점) : $2 ≤ n ≤ 1000, 1 ≤ k ≤ min(n-1, 200)$ - 서브태스크 5 (21점) : $2 ≤ n ≤ 10000, 1 ≤ k ≤ min(n-1, 200)$ - 서브태스크 6 (29점) : $2 ≤ n ≤ 100000, 1 ≤ k ≤ min(n-1, 200)$