/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 7 点
注意
この問題に対する言及は、2021/4/24 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
長さ N の数列 A=(A_1,A_2,...,A_N) と、1 以上 N 以下の整数 K が与えられます。
1 以上 N-K+1 以下の全ての整数 x について、以下の値を求めてください。
- \displaystyle \sum_{i=x}^{x+K-1} A_i 、すなわち、 A_x から A_{x+K-1} までの K 項の総和
制約
- 入力はすべて整数
- 1 \le K \le N \le 5 \times 10^5
- |A_i| \le 10^9 (1 \le i \le N)
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \cdots A_N
出力
N-K+1 行出力せよ。
i 行目には、x=i とした場合の値を出力せよ。
出力する行数が大きくなる場合があるので、注意せよ。
入力例 1
6 3 2 0 2 -1 0 -4
出力例 1
4 1 1 -5
- x=1 としたとき、求める値は A_1 + A_2 + A_3 = 4 です。
- x=2 としたとき、求める値は A_2 + A_3 + A_4 = 1 です。
- x=3 としたとき、求める値は A_3 + A_4 + A_5 = 1 です。
- x=4 としたとき、求める値は A_4 + A_5 + A_6 = -5 です。
Score : 7 points
Warning
Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
Given are a length-N sequence A=(A_1,A_2,...,A_N) and an integer K between 1 and N (inclusive).
For every integer x from 1 through N-K+1, find the following:
- \displaystyle \sum_{i=x}^{x+K-1} A_i, that is, the sum of K elements from A_x through A_{x+K-1}.
Constraints
- All values in input are integers.
- 1 \le K \le N \le 5 \times 10^5
- |A_i| \le 10^9 (1 \le i \le N)
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \cdots A_N
Output
Print N-K+1 lines.
The i-th line should contain the sum for x=i.
Note that you may have to print many lines.
Sample Input 1
6 3 2 0 2 -1 0 -4
Sample Output 1
4 1 1 -5
- The sum for x=1 is A_1 + A_2 + A_3 = 4.
- The sum for x=2 is A_2 + A_3 + A_4 = 1.
- The sum for x=3 is A_3 + A_4 + A_5 = 1.
- The sum for x=4 is A_4 + A_5 + A_6 = -5.