No.1248 Kth Sum

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 17
作問者 : 👑

tute7627 / テスター :

leafirby

9 ProblemId : 4753 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2020-10-03 01:33:30

問題文

長さ $N$ の数列 $A$ が与えられます。
あなたは数列 $A$ を以下の条件を満たすようにいくつかの部分列に分けることにしました。

数列 $A$ の各要素は丁度一つの部分列に含まれる。
分けた後の各部分列の長さは全て $K$ 以上である。

なお、数列の部分列とは数列のいくつかの要素を抜き出し、それらを元の数列における順番のままつなげたものを指します。

分けた後の各部分列の前から

K

番目の要素の和の最小値を求めてください。

入力

 $N K$ 
 $A_{1} A_{2} \dots A_{N}$

$1 \leq N \leq 2 \times 10^{5}$
$1 \leq K \leq N$
$1 \leq A_{i} \leq 10^{9}$

出力

分けた後の各部分列の前から $K$ 番目の要素の和の最小値を求めてください。最後に改行してください。

サンプル

サンプル1

入力

4 2
3 4 1 2

出力

$(3, 1)$ と $(4, 2)$ に分けることで $2$ 番目の要素の和は $1 + 2 = 3$ となります。
$(3, 4, 1, 2)$ と一つの部分列にすることもできますが、 $2$ 番目の要素の和は $4$ となります。
分けた後の各部分列の長さは $2$ 以上である必要があるため、 $(3, 1, 2)$ と $(4)$ に分けることはできません。

サンプル2

入力

3 2
3 4 1

出力

この場合、二つ以上の部分列に分けることはできません。

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