레이팅 미적용전설에 따르면, 성 패트릭은 천 년도 더 전에 무랜드(Mooland)의 모든 뱀을 쫓아냈다. 하지만 그 후로 뱀들이 무랜드로 되돌아왔다! 성 패트릭의 날은 3월 17일이었으므로, 베시는 성 패트릭을 기리기 위해 무랜드의 모든 뱀을 완전히 쫓아내려 한다.
베시는 그물을 갖추고, 직선 위에 \(N\)개의 그룹으로 (\(1 \leq N \leq 400\)) 분포한 뱀들을 포획하려 한다. 베시는 그룹들이 직선 위에 나타나는 순서대로 모든 그룹의 모든 뱀을 포획해야 한다. 한 그룹을 포획할 때마다 베시는 뱀들을 우리에 넣고 다음 그룹을 위해 빈 그물로 다시 시작할 수 있다.
크기가 \(s\)인 그물이 있으면, 베시는 뱀이 \(g\)마리인 그룹을 \(g \leq s\)일 때 포획할 수 있다. 하지만 크기 \(s\)의 그물로 크기 \(g\)의 뱀 그룹을 포획할 때마다 \(s - g\)만큼의 공간을 낭비하게 된다. 베시의 그물은 임의의 크기로 시작할 수 있으며, 베시는 그물의 크기를 \(K\)번 (\(1 \leq K < N\)) 바꿀 수 있다.
모든 그룹을 포획한 후 누적되는 총 낭비 공간의 최솟값을 베시에게 알려주자.
문제 제공: Patrick Zhang
문제 제공: Patrick Zhang
첫째 줄에 \(N\)과 \(K\)가 주어진다. 둘째 줄에 \(N\)개의 정수 \(a_1,\dots,a_N\)이 주어지며, \(a_i\) (\(0 \leq a_i \leq 10^6\))는 \(i\)번째 그룹의 뱀 수이다.
베시가 모든 뱀을 포획한 후의 낭비 공간의 최솟값을 나타내는 정수 하나를 출력한다.
snakes.in · 출력을 쓸 파일 snakes.out6 2
7 9 8 2 3 23Bessie’s net starts at a size of 7. After she captures the first group of
snakes, she changes her net to a size of 9 and keeps that size until the 4th
group of snakes, when she changes her net to size 3. The total wasted space
is \((7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3.\)