시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 966 | 435 | 343 | 45.733% |
Juicy Orange Industry(JOI)는 맛있는 오렌지를 포장해서 출하하는 것이 주된 업무인 회사이다.
JOI사에서는 수집한 N개의 오렌지를 상자에 넣어서 출하한다. 먼저, 오렌지는 공장에 있는 컨베이어 벨트 위에 나란히 놓아야 한다. 컨베이어 벨트 위에 놓여져있는 오렌지는 앞에서부터 순서대로 1부터 N까지 번호가 붙여져 있다. i번째 오렌지의 크기는 Ai이다.
그 다음 작업은 오렌지를 앞에서부터 순서대로 상자에 나눠서 넣는 것이다. 한 상자 넣는 오렌지의 번호는 연속해야 한다.
한 상자에는 최대 M개의 오렌지를 넣을 수 있다. 상자에 오렌지를 넣는 비용은 K + s × (a − b) 로 구할 수 있다. 여기서 a는 상자에 넣은 가장 큰 오렌지의 크기, b는 상자에 넣은 가장 작은 오렌지의 크기, s는 상자에 넣은 오렌지의 개수이다. K는 상자를 포장하는 비용이고, 모든 상자에 공통적으로 적용되는 값이다.
컨베이어 벨트 위에 놓여져 있는 오렌지의 정보와, 한 상자에 넣을 수 있는 오렌지 개수의 최댓값, 상자를 포장하는 비용 K가 주어졌을 때, 모든 오렌지를 포장하는 비용의 최솟값을 구하는 프로그램을 작성하시오.
첫째 줄에 오렌지의 개수 N (1 ≤ N ≤ 20,000), 한 상자에 넣을 수 있는 오렌지 개수의 최댓값 M (1 ≤ M ≤ 1,000, M ≤ N), 상자를 포장하는 비용 K (0 ≤ k ≤ 1,000,000,000)가 주어진다.
둘째 줄부터 N개의 줄에는 오렌지의 크기 Ai (1 ≤ Ai ≤ 1,000,000,000)가 순서대로 주어진다.
첫째 줄에 모든 오렌지를 포장하는 비용의 최솟값을 출력한다.
번호 | 배점 | 제한 |
---|---|---|
1 | 20 | N ≤ 20. |
2 | 50 | N ≤ 2 000, M ≤ 100. |
3 | 30 | 추가적인 제약 조건이 없다. |
6 3 6 1 2 3 1 2 1
21
16 4 12 3 10 13 10 19 9 12 16 11 2 19 9 13 2 13 19
164
16 6 14 19 7 2 15 17 7 14 12 3 14 5 10 17 20 19 12
177
10 1 1000000000 1 1 1 1 1 1 1 1 1 1
10000000000