問題一覧 > 通常問題

No.2548 Problem Selection

レベル : / AI推定難易度 : 800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 86
作問者 : sepa38 / テスター : dyktr_06 InTheBloom Seed57_cash ryota2357
お気に入りにしたユーザー ProblemId : 10365 / 自分の提出
問題文最終更新日: 2023-11-25 12:01:33
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
MMA Contest 017 (順位表) の他の問題:

Problem Statement

Sepa and Yakitori have created a total of $N$ problems for MMA Contest. The difficulty of the $i$-th problem is $A_i$. They will use $M$ of the $N$ problems, but they want to keep the differences in difficulty between problems from becoming large. Therefore, they have decided to create a problem set that minimizes the value $S$ defined by the following rules.

  • Let $B_i$ be the difficulty of the problem with the $i$-th smallest difficulty among the selected problems.
  • $\displaystyle{S = \sum_{i=1}^{M-1} (B_{i+1} - B_i)^2}$

Output the minimum value of $S$.

Input

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

Constraints

  • All inputs are integers.
  • $1 \leq M \leq N \leq 10^5$
  • $1 \leq A_i \leq 10^9$

Output

Output the result on $1$ line.

Sample

Sample 1
Input
5 3
7 6 2 9 5
Output
2

If problems $1, 2, 5$ are selected, then $S = (6 - 5)^2 + (7 - 6)^2 = 2$, which is the minimum value.

Sample 2
Input
10 5
227930076 836334727 108597970 656892815 455743732 901045388 302006162 256603330 228958951 169578258
Output
6231622091586614

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