177. Running Sum of the Last K
Foundation1000 ms256 MBSolved by 0%
Values arrive one at a time. After each one, print the sum of the most recent
k values, or of everything so far, if fewer than k have arrived.
The window slides: when a new value arrives and the window is already full, the OLDEST value leaves. That is a queue, and it is why you never have to add the window up again from scratch.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k ≤ 200000` - `-1000000 ≤ value ≤ 1000000`
Input
The first line contains two integers n and k, how many values arrive, and the window size.
The second line contains n space-separated integers, in arrival order.
Output
Print n integers on ONE line, separated by single spaces, the window sum after each arrival.
Input5 3
1 2 3 4 5
Output1 3 6 9 12
Notefills the window and then slides it
Input1 1
7
Output7
Noteis a single value with a window of one
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.