F - NPCの家 (NPC's House)
Editorial
/
Time Limit: 1 sec / Memory Limit: 256 MB
問題文
NPCの動きを確認したjoisinoお姉ちゃんは、今度はNPCの家の配置を任された。
左右に無限に伸びる直線上に、N人のNPCが立っている。
そして、その直線上にM軒のNPCの家を設置する。
そして、各NPCは自分に最も近い家へと戻ることになる。
このゲームでは、NPCの家は、リアリティーを追求するために、各NPCが家に戻るまでの距離の合計を最小化する位置に家を設置しなければならない。
この作業を効率よくすすめるため、joisinoお姉ちゃんは各NPCが家に戻るまでの距離の合計の最小値を求めるプログラムを書くことにした。
入力
入力は以下の形式で標準入力から与えられる。
N M X_1 X_2 : X_N
- 1行目には、NPCの数N、設置する家の数Mが与えられる。(1 ≦ N ≦ 1000, 1 ≦ M ≦ 1000)
- 次のN行のうちi行目には、X_iが与えられ、i番目のNPCの位置を表している。(-10^9 ≦ X_i ≦ 10^9)
配点
この問題には部分点が設定されている。
- データセット1は、N ≦ 300, M ≦ 300を満たし、正解すると10点を得られる。
- データセット2では追加の制約はなく、正解すると110点を得られる。
出力
各NPCが家に戻るまでの距離の合計の最小値を出力せよ。
入力例1
5 2 -3 -1 0 2 5
出力例1
6
- 例えば、-1, 2の位置に家をおいた時、NPC1, 2, 3は-1の位置の家に戻り、NPC4, 5は2の位置の家へ戻るので、各NPCが家に戻るまでの距離の合計は2 + 0 + 1 + 0 + 3 = 6となる。
- そして、これよりも各NPCが家に戻るまでの距離の合計を小さくする配置はないため、6が答えとなる。
入力例2
10 3 -3 12 -92 -45 -15 27 14 94 -39 75
出力例2
131