atcoder#ABC281E. [ABC281E] Least Elements

[ABC281E] Least Elements

配点 : 500500

問題文

長さ NN の整数列 A=(A1,,AN)A = (A_1, \dots, A_N) と整数 M,KM, K が与えられます。 i=1,,NM+1i = 1, \dots, N - M + 1 に対して、次の独立な問題を解いてください。

MM 個の整数 Ai,Ai+1,,Ai+M1A_i, A_{i + 1}, \dots, A_{i + M - 1} を昇順に並べ替えたときの先頭 KK 個の値の総和を求めよ。

制約

  • 1KMN2×1051 \leq K \leq M \leq N \leq 2 \times 10^5
  • 1Ai1091 \leq A_i \leq 10^9
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

NN MM KK

A1A_1 A2A_2 \ldots ANA_N

出力

i=ki = k のときの問題の答えを answerk\mathrm{answer}_k として、次の形式で出力せよ。

answer1\mathrm{answer}_1 answer2\mathrm{answer}_2 \ldots answerNM+1\mathrm{answer}_{N-M+1}

6 4 3
3 1 4 1 5 9
5 6 10
  • i=1i = 1 のとき、Ai,Ai+1,Ai+2,Ai+3A_i, A_{i+1}, A_{i+2}, A_{i+3} を小さい順に並べると 1,1,3,41, 1, 3, 4 となり、小さい方から 33 個の値の総和は 55 です。
  • i=2i = 2 のとき、Ai,Ai+1,Ai+2,Ai+3A_i, A_{i+1}, A_{i+2}, A_{i+3} を小さい順に並べると 1,1,4,51, 1, 4, 5 となり、小さい方から 33 個の値の総和は 66 です。
  • i=3i = 3 のとき、Ai,Ai+1,Ai+2,Ai+3A_i, A_{i+1}, A_{i+2}, A_{i+3} を小さい順に並べると 1,4,5,91, 4, 5, 9 となり、小さい方から 33 個の値の総和は 1010 です。
10 6 3
12 2 17 11 19 8 4 3 6 20
21 14 15 13 13