Score : $500$ points

问题描述

你给定一个整数序列 $A = (A_1, \dots, A_N)$，其长度为 $N$，以及整数 $M$ 和 $K$。
对于每个 $i = 1, \dots, N - M + 1$，独立解决以下问题。

求在升序排列的 $M$ 个整数 $A_i, A_{i + 1}, \dots, A_{i + M - 1}$ 的有序列表中，前 $K$ 个值的和。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 11:48:29