オレンジの出荷 (Oranges)

## 题目描述 CXR决定将收获的$n$个橙子分装进一些箱子内。在NXY的工厂中，橙子排列在输送带上，依次编号为$1...n$。橙子$i(1\leq i\leq n$)的大小为$A_i$。由于分拣不方便，同一个箱子内，橙子的编号必须连续。 一个箱子内最多可以装$m$个橙子。在一个箱子内装一些橙子的成本为$k+s\times (a-b)$。$k$是箱子本身的成本，所有箱子的成本一样。$s$是该箱子中橙子的数目。 $a$是该箱子中最大橙子的大小，$b$是该箱子中最小橙子的大小。 求包装这$n$个橙子所需的最小成本。 ## 输入格式 第一行有三个整数$n,m,k$，用空格分隔。 在接下来的$n$行中，第$i$行$(1\leq i\leq n)$有一个整数$A_i$。 输入的所有数的含义见题目描述。 ## 输出格式 输出一个整数，表示包装这$n$个橙子所需的最小成本。 ## 输入样例 1 ``` 6 3 6 1 2 3 1 2 1 ``` ## 输出样例 1 ``` 21 ``` ## 输入样例 2 ``` 16 4 12 3 10 13 10 19 9 12 16 11 2 19 9 13 2 13 19 ``` ## 输出样例 2 ``` 164 ``` ## 样例输入 3 ``` 16 6 14 19 7 2 15 17 7 14 12 3 14 5 10 17 20 19 12 ``` ## 样例输出 3 ``` 177 ``` ## 样例输入 4 ``` 10 1 1000000000 1 1 1 1 1 1 1 1 1 1 ``` ## 样例输出 4 ``` 10000000000 ``` ## 样例解释 4 答案可能会爆$int$。 ## 数据范围 - 1≤N≤20 000 - 1≤M≤1 000 - 0≤K≤1 000 000 000 - 1≤A_i≤1 000 000 000 (1≤i≤N) - M≤N 本题：JOI 2016 Final T1「オレンジの出荷」

[problemUrl]: https://atcoder.jp/contests/joi2016ho/tasks/joi2016ho_a あなたは Juicy Orange Industry 社を知っているだろうか? この会社の業務は美味しいオレンジを栽培して出荷することである．ここでは略して JOI 社と呼ぶ． JOI 社では，収穫された $ N $ 個のオレンジを箱詰めして出荷することになった．オレンジは工場にあるベルトコンベアの上に並べられており，ベルトコンベアの前から順番に $ 1 $ から $ N $ までの番号が付けられている．オレンジは大小さまざまであり，オレンジ $ i $ ($ 1\ \leqq\ i\ \leqq\ N $) の大きさは $ A_i $ である． これらのオレンジを前から順番にいくつかの箱に分けて詰める．ひとつの箱には連続した番号のオレンジしか詰めることができない． ひとつの箱には最大で $ M $ 個までのオレンジを詰めることができる．ある箱にいくつかのオレンジを詰めるためにかかるコストは，箱に詰める最大のオレンジの大きさを $ a $，箱に詰める最小のオレンジの大きさを $ b $，箱に詰めるオレンジの個数を $ s $ としたときに，$ K\ +\ s\ \times\ (a\ -\ b) $ で求めることができる．ここで，$ K $ は箱にかかるコストであり，すべての箱で共通の値である． 適切な個数の箱を用意して，すべてのオレンジを適切に箱詰めすることで，箱詰めにかかるコストの総和をできるだけ小さくしたい．

標準入力から以下の入力を読み込め． - $ 1 $ 行目には，$ 3 $ 個の整数 $ N,\ M,\ K $ が空白を区切りとして書かれている．これは，オレンジが $ N $ 個あり，ひとつの箱に詰められるオレンジの個数の最大値が $ M $ であって，箱にかかるコストが $ K $ であることを表す． - 続く $ N $ 行のうちの $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ N $) には，整数 $ A_i $ が書かれている．これは，オレンジ $ i $ の大きさが $ A_i $ であることを表す．

標準出力に，箱詰めにかかるコストの総和の最小値を $ 1 $ 行で出力せよ． - - - - - -

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

### 課題 ベルトコンベア上に並んでいるオレンジの情報と，ひとつの箱に詰められるオレンジの個数の最大値および，箱にかかるコストが与えられたとき，箱詰めにかかるコストの総和の最小値を求めるプログラムを作成せよ． - - - - - - ### 制限 すべての入力データは以下の条件を満たす． - $ 1\ \leqq\ N\ \leqq\ 20\,000 $． - $ 1\ \leqq\ M\ \leqq\ 1\,000 $． - $ 0\ \leqq\ K\ \leqq\ 1\,000\,000\,000 $． - $ 1\ \leqq\ A_i\ \leqq\ 1\,000\,000\,000 $ ($ 1\ \leqq\ i\ \leqq\ N $)． - $ M\ \leqq\ N $． ### 小課題 #### 小課題 1 \[20 点\] - $ N\ \leqq\ 20 $ を満たす． #### 小課題 2 \[50 点\] 以下の条件を満たす． - $ N\ \leqq\ 2\,000 $． - $ M\ \leqq\ 100 $． #### 小課題 3 \[30 点\] 追加の制限はない． - - - - - - ### Sample Explanation 1 $ 1 $ 番目の箱にオレンジ $ 1 $ からオレンジ $ 3 $ までの $ 3 $ 個のオレンジを詰め，$ 2 $ 番目の箱にオレンジ $ 4 $ からオレンジ $ 6 $ までの $ 3 $ 個のオレンジを詰めると，箱詰めにかかるコストの総和は $ (6\ +\ 3\ \times\ (3\ -\ 1))\ +\ (6\ +\ 3\ \times\ (2\ -\ 1))\ =\ 21 $ となる． どのように詰めても箱詰めにかかるコストの総和が $ 21 $ を下回ることはないので，$ 21 $ を出力する． - - - - - - ### Sample Explanation 2 $ 11 $ 個の箱を用意して，それぞれの箱に前から順に $ 1 $ 個，$ 3 $ 個，$ 1 $ 個，$ 1 $ 個，$ 3 $ 個，$ 1 $ 個，$ 1 $ 個，$ 2 $ 個，$ 1 $ 個，$ 1 $ 個，$ 1 $ 個のオレンジを詰めることで，箱詰めにかかるコストの総和が最小となる． - - - - - - ### Sample Explanation 3 \- - - - - - ### Sample Explanation 4 答えが $ 32 $ ビット符号付き整数の範囲に収まるとは限らないことに注意せよ．