| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 129 | 24 | 22 | 21.359% |
최근 적군의 동향이 심상치 않다는 점을 보고받은 지휘관은, 접경 지역에 감시초소를 설치하여 모든 접경 지역을 완벽히 감시하고자 한다. 접경 지역은 $1$번 지역부터 $N$번 지역까지 $N$개가 있으며, 거리 $1$의 간격을 두고 왼쪽부터 오른쪽까지 일렬로 나열되어 있다. 단, 접경 지역의 길이는 $0$이라고 가정한다. 각 지역에 감시초소를 설치하기 위해선 각각 $c_i$의 비용을 부담해야 하며, 각각의 접경 지역에는 하나의 감시초소만 설치할 수 있다.
각각의 감시초소에는 최소한 한 명의 병사가 분대장으로 배치되어야 하며, 분대장은 항상 감시초소가 설치되어 있는 지역을 감시한다. 감시초소에 병사를 추가로 배치하여 더 많은 지역을 감시할 수 있는데, 거리가 $x$만큼 떨어진 지역 하나를 추가로 감시하기 위해선 $x+1$명의 병사를 추가로 배치해야 한다. 또한, 감시초소들이 감시하는 영역이 교차하면 혼동이 생길 것을 우려한 지휘관은, 반드시 각각의 감시초소에서 연속적인 지역들만을 감시하도록 지시했다.
그러나, 건설할 수 있는 감시초소의 크기가 작아 각각의 감시초소에는 최대 $P$명의 병사까지만 배치할 수 있다고 한다. 지휘관을 위해, 모든 접경 지역을 감시하기 위해 필요한 최소 비용을 구하여라.
첫 번째 줄에 접경 지역의 개수 $N$과 각각의 감시초소에 배치할 수 있는 최대 인원수 $P$가 공백으로 구분되어 정수로 주어진다.
두 번째 줄에 $i$번 지역에 감시초소를 건설하는 비용 $c_i$가 공백으로 구분되어 정수로 주어진다.
모든 접경 지역을 감시하기 위해 필요한 최소 비용을 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 40 | $N\leq 15$ |
| 2 | 75 | $N\leq 100$ |
| 3 | 40 | $N\leq 5\,000$ |
| 4 | 95 | 추가 제한 없음 |
5 5 10 8 3 6 1
9
$2$번 지역에 병사 $5$명을 배치하여 $1, 2, 3$번 지역을 감시하고, $5$번 지역에 병사 $3$명을 배치하여 $4, 5$번 지역을 감시하면 $9$의 비용으로 모든 지역을 감시할 수 있다.
6 6 9 8 1 10 3 99
4
Contest > 보라매컵 > 제2회 보라매컵 예선 E번