/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ N の整数列 A = (A_1, \dots, A_N) と整数 M, K が与えられます。
i = 1, \dots, N - M + 1 に対して、次の独立な問題を解いてください。
M 個の整数 A_i, A_{i + 1}, \dots, A_{i + M - 1} を昇順に並べ替えたときの先頭 K 個の値の総和を求めよ。
制約
- 1 \leq K \leq M \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K A_1 A_2 \ldots A_N
出力
i = k のときの問題の答えを \mathrm{answer}_k として、次の形式で出力せよ。
\mathrm{answer}_1 \mathrm{answer}_2 \ldots \mathrm{answer}_{N-M+1}
入力例 1
6 4 3 3 1 4 1 5 9
出力例 1
5 6 10
- i = 1 のとき、A_i, A_{i+1}, A_{i+2}, A_{i+3} を小さい順に並べると 1, 1, 3, 4 となり、小さい方から 3 個の値の総和は 5 です。
- i = 2 のとき、A_i, A_{i+1}, A_{i+2}, A_{i+3} を小さい順に並べると 1, 1, 4, 5 となり、小さい方から 3 個の値の総和は 6 です。
- i = 3 のとき、A_i, A_{i+1}, A_{i+2}, A_{i+3} を小さい順に並べると 1, 4, 5, 9 となり、小さい方から 3 個の値の総和は 10 です。
入力例 2
10 6 3 12 2 17 11 19 8 4 3 6 20
出力例 2
21 14 15 13 13
Score : 500 points
Problem Statement
You are given an integer sequence A = (A_1, \dots, A_N) of length N, and integers M and K.
For each i = 1, \dots, N - M + 1, solve the following independent problem.
Find the sum of the first K values in the sorted list of the M integers A_i, A_{i + 1}, \dots, A_{i + M - 1} in ascending order.
Constraints
- 1 \leq K \leq M \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M K A_1 A_2 \ldots A_N
Output
Let \mathrm{answer}_k be the answer to the problem for i = k, and print them in the following format:
\mathrm{answer}_1 \mathrm{answer}_2 \ldots \mathrm{answer}_{N-M+1}
Sample Input 1
6 4 3 3 1 4 1 5 9
Sample Output 1
5 6 10
- For i = 1, sorting A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1, 1, 3, 4, where the sum of the first three values is 5.
- For i = 2, sorting A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1, 1, 4, 5, where the sum of the first three values is 6.
- For i = 3, sorting A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1, 4, 5, 9, where the sum of the first three values is 10.
Sample Input 2
10 6 3 12 2 17 11 19 8 4 3 6 20
Sample Output 2
21 14 15 13 13