問題一覧 > 通常問題

No.2548 Problem Selection

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 82
作問者 : sepa38sepa38 / テスター : dyktr_06dyktr_06 InTheBloomInTheBloom Seed57_cashSeed57_cash ryota2357ryota2357
0 ProblemId : 10365 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-11-25 12:01:33

問題文

sepa くんとやきとりくんは MMA Contest のために合計 $N$ 問だけ問題を作りました。$i$ 番目の難易度は $A_i$ です。 $N$ 問のうち $M$ 問を出題しますが、問題間の難易度差が大きくならないようにしたいです。 そこで、以下のルールで定義される値 $S$ が最小の問題セットを作ることにしました。

  • 選んだ問題のうち、難易度が $i$ 番目に小さい問題の難易度を $B_i$ とおく
  • $\displaystyle{S = \sum_{i=1}^{M-1} (B_{i+1} - B_i)^2}$

$S$ の最小値を出力してください。

入力

$N \ M$
$A_1 \ A_2 \ \cdots \ A_N$

制約

  • 入力はすべて整数である。
  • $1 \leq M \leq N \leq 10^5$
  • $1 \leq A_i \leq 10^9$

出力

計算結果を $1$ 行に出力してください。

サンプル

サンプル1
入力
5 3
7 6 2 9 5
出力
2

$1, 2, 5$ 問目を選ぶと、$S = (6 - 5)^2 + (7 - 6)^2 = 2$ となり、これが最小値です。

サンプル2
入力
10 5
227930076 836334727 108597970 656892815 455743732 901045388 302006162 256603330 228958951 169578258
出力
6231622091586614

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。