1661D - Progressions Covering - CodeForces Solution

from sys import stdin, setrecursionlimit
input = stdin.readline
from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache, reduce
from heapq import heappush, heappop
from math import sqrt, ceil, floor, log2

def x(t = int):
    return list(map(t, input().split()))

n, k = x()
a = x()
carry = 0
ret = 0
lastK = 0
d = deque()
for i in range(n - 1, -1, -1):
    need = max(0, a[i] - carry)
    val = min(k, i+1)
    add = ceil(need / val)
    ret += add
    d.append(add)
    if len(d) > k:
        lastK -= d.popleft()
    carry += (val - 1) * add
    carry -= lastK
    
    lastK += add

print(ret)