수열 Batch
시간 제한 | 메모리 제한 | 제출 횟수 | 제출한 사람 수 | 해결한 사람 수 | 정답률 |
---|---|---|---|---|---|
2000 ms | 128 MiB | 10090 | 939 | 665 | 70.82% |
음수가 아닌 자연수 $n$개가 원소인 수열을 가지고 어떤 게임을 하려고 한다. 이 게임에서는 수열을 $k+1$개의 부분으로 나누어야 한다. 수열을 $k+1$개의 부분으로 나누기 위해서 다음의 과정을 $k$번 반복한다.
- 두 개 이상의 자연수를 가진 부분을 선택한다. (처음에는 수열 전체가 하나의 부분이다.)
- 선택된 부분의 연속한 두 원소 사이를 자르는 것으로 두 부분이 만들어진다. 이 과정을 한번 할 때 마다 점수를 얻는데, 그 점수는 만들어진 각 부분에 있는 수들을 합하여 얻는 두 수의 곱이다. 전체 과정에서 얻는 점수의 합을 최대로 하고 싶다.
입력
입력의 첫 번째 줄에는 자연수 두 개가 주어지는데 각각 $n$과 $k$이다. ($k+ 1 < n$) 두 번째 줄에는 입력수열이 $n$개의 음수가 아닌 자연수로 주어진다. 각 수는 0 이상 $10^4$ 이하이다.
출력
입력의 첫 줄에 얻을 수 있는 가장 큰 점수를 출력한다. 입력의 둘째 줄에는 $k$개의, 1 이상 $n-1$ 이하인 자연수를 출력하는데, 이들은 가장 큰 점수를 얻기 위해 수열을 자르는 방법을 (최초 수열에서의) 위치로 제시한 것이다. 위치는 수열을 자르는 곳 바로 앞에 있는 원소의 위치이다. 즉, 4번째와 5번째 수 사이를 잘랐다면 4를 출력하는 것이다.
최대의 점수를 얻는 방법이 여러 가지가 있다면 그 중 아무 것이나 하나를 출력하면 된다.
입출력 예
입력
7 3
4 1 3 4 0 2 3
출력
108
1 3 5
추가설명
입출력 예에서 108점을 얻는 방법은 아래와 같다.
- 처음에 전체 수열인 $(4, 1, 3, 4, 0, 2, 3)$이 있다. 이 수열을 첫 번째 원소 다음에서 잘라서 $52$점($= 4 \times (1+ 3 +4 + 0 +2 + 3)$)을 얻는다.
- 이제 $(4)$와 $(1, 3, 4, 0, 2, 3)$의 두 부분이 생기는데 이를 세 번째 원소 다음에서 잘라서 $36$점($= (1 +3) \times (4 + 0+ 2 +3)$)을 얻는다.
- 이제 $(4)$, $(1, 3)$, $(4, 0, 2, 3)$의 세 부분이 있는데 이를 다섯 번째 원소 다음에서 잘라서 $20$점($= (4 +0) \times (2 + 3)$)을 얻는다.
최종적으로 네 부분 $(4)$, $(1, 3)$, $(4, 0)$, $(2, 3)$이 남고, 얻는 점수는 $52 + 36 + 20 = 108$점이다.
채점
다음과 같은 여섯 개의 서브태스크로 채점이 이루어 진다.
- (11점) $1 \le k < n \le 10$
- (11점) $1 \le k < n \le 50$
- (11점) $1 \le k < n \le 200$
- (17점) $2 \le n \le 1000$, $1 \le k \le \min (n-1, 200)$
- (21점) $2 \le n \le 10000$, $1 \le k \le \min (n-1, 200)$
- (29점) $2 \le n \le 100000$, $1 \le k \le \min (n-1, 200)$
문제 출처