조삼모사
시간 제한2초메모리 제한128 MB
일렬로 놓인 바나나 N개를 개별로 옮기거나 연속된 K개씩 묶어 C초에 옮길 수 있을 때, 최소 이동 시간과 그때 필요한 묶음 이동 횟수 및 위치를 구하는 문제입니다.
문제
동물원에서 탈출한 원숭이가 일렬로 놓인 N개의 바나나를 모두 은신처로 옮기려고 한다.
원숭이는 두 가지 방법으로 바나나를 옮길 수 있다.
- 바나나 한 개를 옮긴다. 걸리는 시간은 그 바나나의 무게와 같다.
- 처음 놓인 순서에서 연속한 K개의 바나나를 한꺼번에 옮긴다. 걸리는 시간은 항상 C이다.
은신처에서 배급소로 돌아오는 데 걸리는 시간은 0초이다. 원숭이는 바나나를 들고 있지 않을 때 순간이동할 수 있기 때문이다.
N개 바나나의 무게가 주어질 때, 모든 바나나를 옮기는 데 필요한 최소 시간을 구하시오. 최소 시간이 되는 방법이 여러 가지라면, K개를 한꺼번에 옮기는 횟수가 가장 적은 방법을 선택해야 한다.
입력
첫째 줄에 바나나의 개수 N이 주어진다. N은 1 이상 1,000,000 이하이다.
둘째 줄에 K와 C가 주어진다. K와 C는 각각 1 이상 10,000 이하이다.
셋째 줄에 바나나의 무게를 나타내는 N개의 자연수가 처음 놓인 순서대로 주어진다. 각 무게는 1 이상 1,000 이하이다.
출력
첫째 줄에 모든 바나나를 옮기는 최소 시간을 출력한다.
둘째 줄에 K개를 한꺼번에 옮기는 횟수를 출력한다.
셋째 줄에는 그때 선택한 각 묶음의 왼쪽 위치를 오름차순으로 출력한다. 위치는 1부터 시작한다. 선택한 묶음이 없으면 빈 줄을 출력한다.
최소 시간과 최소 횟수를 모두 만족하는 방법이 여러 가지라면 아무 방법이나 출력해도 된다.