003 - 結界とオブジェと魔法地蔵と

注意

問題読みたくない人は、問題概要まで読み飛ばしてくださいm(_ _)m

問題

アリス・マーガトロイドの住む魔法の森。

人里に「アリス同盟」なるものが存在することを知ったアリスは身の危険を感じ、

魔法の森の自宅周辺に結界を張ることに決めた。

アリスはm個のオブジェを結界のカギとして、それを配置する場所を探している内に、

魔法地蔵の矢田寺成美と出会ったのだった・・・

アリス：「あら、成美ちゃんじゃない」

成美　：「あ、アリス！どうしたの？こんなところで」

アリス：「最近物騒だから、家の周りに結界を張ろうと思っているのよ」

成美　：「へ〜そうなんだ。なんだか怖いね。私、心細くなってきちゃった」

アリス：「そういえば、あなたはいつもひとりでいるわよね？」

成美　：「うん・・・ひとりでいるのは好きだけど、でも少し寂しいなって・・・」

アリス：「そう・・・あなたのために何かしてあげられないかしら・・・

　　　　　そうだ！今結界を張るためにオブジェを置く場所を探しているの。

　　　　　それで、この付近にオブジェを設置しようと思うの。

　　　　　それなら、ひとりでいても少しは寂しさもまぎれると思うんだけど・・・どうかしら？」

成美　：「アリス・・・うん！いいアイディアだね！ありがとう！」

アリスは成美のためにこの付近でm個のオブジェを設置することに決めた。オブジェは一直線上に設置する。

しかし、魔法の森は木々が密集しており、オブジェを設置できそうな開けた場所はこの付近にn箇所しかない。

また、オブジェ同士の距離が離れれば離れるほど結界の力が弱まってしまうため、できるだけ隣り合うオブジェ同士を近づけたい。

アリスと成美のためにも、隣り合うオブジェ同士の距離の最大値を最小化してほしい。

問題概要

オブジェを設置できる箇所数 n 、オブジェの数 m 、成美のいる場所から地点 i までの距離 d_i が与えられるため、

m 個のオブジェを並べたとき、隣り合うオブジェ同士の距離の最大値を最小化した値を出力せよ。

入力

一行目に地点数n、オブジェの数mが与えられる。

続くn行に成美のいる場所から地点iまでの距離d_iが与えられる。

n m
d1
・
・
・
dn

出力

隣り合うオブジェ同士の距離の最大値を最小化した値を出力せよ。最後に改行すること。

制約

全ての入力ケースについて以下を満たす。

• 2 ≦ n ≦ 10⁵
• 2 ≦ m ≦ n
• -10⁸ ≦ d ≦ 10⁸

---

入出力例

入力例1

5 3
1
8
4
9
2

出力例1

2

解説

1、2、4の地点に設置するのが最適解である。

入力例2

2 2
-5
5

出力例2

10

dが負の値になることもあるため注意せよ。

作者コメント

新キャラの成美ちゃん出してみたけど、成美ちゃんの口調これでいいかなぁ・・・

成美ちゃんクラスタから反感買ったらどうしよ・・・