Least Elements

题目描述

你被给定一个长度为 $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$ 个值的和。

输入格式

输入按下列格式从标准输入给出： $N$ $M$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

设 $\mathrm{answer}_k$ 为 $i = k$ 时问题的答案，并按下列格式输出： $\mathrm{answer}_1$ $\mathrm{answer}_2$ $\ldots$ $\mathrm{answer}_{N-M+1}$

6 4 3
3 1 4 1 5 9

5 6 10

10 6 3
12 2 17 11 19 8 4 3 6 20

21 14 15 13 13

提示

$1 \leq K \leq M \leq N \leq 2 \times 10^5$ $1 \leq A_i \leq 10^9$ 输入中的所有数值均为整数。当 $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$.

标签: AtCoder|abc281E

来源

AtCoder|abc281E