配点 : 500 点
問題文
長さ N の整数列 A=(A1,…,AN) と整数 M,K が与えられます。
i=1,…,N−M+1 に対して、次の独立な問題を解いてください。
M 個の整数 Ai,Ai+1,…,Ai+M−1 を昇順に並べ替えたときの先頭 K 個の値の総和を求めよ。
制約
- 1≤K≤M≤N≤2×105
- 1≤Ai≤109
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K
A1 A2 … AN
出力
i=k のときの問題の答えを answerk として、次の形式で出力せよ。
answer1 answer2 … answerN−M+1
6 4 3
3 1 4 1 5 9
5 6 10
- i=1 のとき、Ai,Ai+1,Ai+2,Ai+3 を小さい順に並べると 1,1,3,4 となり、小さい方から 3 個の値の総和は 5 です。
- i=2 のとき、Ai,Ai+1,Ai+2,Ai+3 を小さい順に並べると 1,1,4,5 となり、小さい方から 3 個の値の総和は 6 です。
- i=3 のとき、Ai,Ai+1,Ai+2,Ai+3 を小さい順に並べると 1,4,5,9 となり、小さい方から 3 個の値の総和は 10 です。
10 6 3
12 2 17 11 19 8 4 3 6 20
21 14 15 13 13