問題一覧 > 通常問題

No.1248 Kth Sum

レベル : / AI推定難易度 : 2025 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 17
作問者 : 👑 tute7627 / テスター : leafirby
お気に入りにしたユーザー ProblemId : 4753 / 自分の提出
問題文最終更新日: 2020-10-03 01:33:30
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
yukicoder contest 268 (順位表) の他の問題:

Problem Statement

You are given a sequence $A$ of length $N$.
You decide to split the sequence $A$ into several subsequences so that the following conditions are satisfied.

  • Each element of the sequence $A$ is contained in exactly one subsequence.
  • The length of every subsequence after the split is at least $K$.
Here, a subsequence of a sequence is obtained by extracting some elements of the sequence and concatenating them in their original order.

Find the minimum possible sum of the $K$-th elements from the front of the subsequences after the split.

Input

$N\ K$
$A_1 \ A_2 \dots A_N$

  • $1 \le N \le 2 \times 10^5$
  • $1 \le K \le N$
  • $1 \le A_i \le 10^9$

Output

Output the minimum possible sum of the $K$-th elements from the front of the subsequences after the split. Print a newline at the end.

Sample

Sample 1
Input
4 2
3 4 1 2
Output
3

By splitting into $(3,1)$ and $(4,2)$, the sum of the $2$-nd elements is $1+2=3$.
You can also keep it as the single subsequence $(3,4,1,2)$, but then the sum of the $2$-nd elements is $4$.
Since the length of every subsequence after the split must be at least $2$, you cannot split into $(3,1,2)$ and $(4)$.

Sample 2
Input
3 2
3 4 1
Output
4

In this case, it is not possible to split into two or more subsequences.

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