E - 天下一合体
Editorial
/
Time Limit: 7 sec / Memory Limit: 256 MB
配点 : 900 点
問題文
タカハシ君は長さ N の数列 a_1, a_2, ..., a_N を持っています。そして以下の動作を何度も行います。
- 数列から、隣り合う 2 つの要素を選ぶ。そしてその 2 つの要素を足して 1 つにする。つまり 2 つの要素を、要素の和を値に持つ 1 つの要素で置き換える。
なお、操作は数列の要素数が M 未満にならない限り好きな回数行えます。
タカハシ君は数列の各要素の絶対値の合計を最小化したいです。あなたの仕事はタカハシ君の代わりに、この最小を求めることです。
制約
- 1 ≦ N ≦ 20,000
- 1 ≦ M ≦ min(100, N)
- |a_i| ≦ 10^9
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 a_2 ... a_N
出力
1 行に求めた答えを出力してください。 出力の末尾に改行を入れること。
入力例 1
4 2 2 -4 3 -1
出力例 1
2
- 最初は[2, -4, 3, -1]の1つ目と2つ目の要素を選びます。すると[-2, 3, -1]になります。
- 次に[-2, 3, -1]の1つ目と2つ目の要素を選びます。すると[1, -1]になります。
すると求める値は |1| + |-1| = 2 になり、これが最適です。
入力例 2
9 3 0 3 -5 -1 5 0 -3 5 -4
出力例 2
2
- 2つ目と3つ目の要素を選ぶ操作を5回行います。すると[0, -1, 5, -4]になります。
- 次に3つ目と4つ目を選び[0, -1, 1]にします。
すると求める値は |0| + |-1| + |1| = 2 になり、これが最適です。
入力例 3
5 5 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
5000000000