Editorial for Sensor Blocking

Editorial

We can iterate through the array from left to right. When we see a sensor which needs blocking, we place down however many pieces of foil we need to cover it. We need to remember that this foil will already partially take care of the next $k$ sensors, so we add the amount of foil we add to a variable $c$. We need to remember to subtract it again after $k$ iterations, so we add it to an array that keeps track of what to subtract. At every sensor with strength $s$, the amount of foil we need to add will obviously be $s - c$. Every time we add foil we add it to the total, which is what we return.

Implementation

n, k = map(int, input().split())
a = list(map(int, input().split()))

cur = 0
end = [0] * n
total = 0

for i in range(n):
    cur -= end[i]
    if a[i] <= cur:
        continue
    q = a[i] - cur
    cur += q
    total += q
    if i + k < n:
        end[i + k] = q

print(total)