Progressions Covering
You are given two arrays: an array $$$a$$$ consisting of $$$n$$$ zeros and an array $$$b$$$ consisting of $$$n$$$ integers.You can apply the following operation to the array $$$a$$$ an arbitrary number of times: choose some subsegment of $$$a$$$ of length $$$k$$$ and add the arithmetic progression $$$1, 2, \ldots, k$$$ to this subsegment — i. e. add $$$1$$$ to the first element of the subsegment, $$$2$$$ to the second element, and so on. The chosen subsegment should be inside the borders of the array $$$a$$$ (i.e., if the left border of the chosen subsegment is $$$l$$$, then the condition $$$1 \le l \le l + k - 1 \le n$$$ should be satisfied). Note that the progression added is always $$$1, 2, \ldots, k$$$ but not the $$$k, k - 1, \ldots, 1$$$ or anything else (i.e., the leftmost element of the subsegment always increases by $$$1$$$, the second element always increases by $$$2$$$ and so on).Your task is to find the minimum possible number of operations required to satisfy the condition $$$a_i \ge b_i$$$ for each $$$i$$$ from $$$1$$$ to $$$n$$$. Note that the condition $$$a_i \ge b_i$$$ should be satisfied for all elements at once.
Consider the first example. In this test, we don't really have any choice, so we need to add at least five progressions to make the first element equals $$$5$$$. The array $$$a$$$ becomes $$$[5, 10, 15]$$$.Consider the second example. In this test, let's add one progression on the segment $$$[1; 3]$$$ and two progressions on the segment $$$[4; 6]$$$. Then, the array $$$a$$$ becomes $$$[1, 2, 3, 2, 4, 6]$$$.
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$) — the number of elements in both arrays and the length of the subsegment, respectively.The second line of the input contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^{12}$$$), where $$$b_i$$$ is the $$$i$$$-th element of the array $$$b$$$.
Print one integer — the minimum possible number of operations required to satisfy the condition $$$a_i \ge b_i$$$ for each $$$i$$$ from $$$1$$$ to $$$n$$$.
(n, k) = [*map(int, input().split())]
b = [*map(int, input().split())]
d = [0] * n
s = total = 0
nhsbw = 0
dhyd = 0
for i in range(n - 1, -1, -1):
    b[i] -= total
    if b[i] > 0:
        dd = min(k, i + 1)
        d[i] = (b[i] + dd - 1) // dd
    s += d[i] - (d[i + k] if i + k < n else 0)
    total += d[i] * dd - s
print(sum(d))
(n, k) = [*map(int, input().split())]
b = [*map(int, input().split())]
d = [0] * n
s = total = 0
for i in range(n - 1, -1, -1):
    b[i] -= total
    if b[i] > 0:
        dd = min(k, i + 1)
        d[i] = (b[i] + dd - 1) // dd
    s += d[i] - (d[i + k] if i + k < n else 0)
    total += d[i] * dd - s
print(sum(d))
def main():
    (n, k) = map(int, input().split())
    b = list(map(int, input().split()))
    temp = 0
    operations = [0] * n
    last = 0
    for i in range(n - 1, k - 1, -1):
        now = 0
        if i != n - 1:
            last -= temp
            now = last
            if i + k >= n:
                pass
            else:
                temp -= operations[i + k]
        delta = b[i] - now
        if delta <= 0:
            continue
        else:
            operations[i] = (delta + k - 1) // k
            temp += operations[i]
            last = operations[i] * k + now
    m = 0
    need = [0] * k
    for i in range(k - 1, -1, -1):
        if i != n - 1:
            last -= temp
            need[i] = max(0, b[i] - last)
            if i + k >= n:
                pass
            else:
                temp -= operations[i + k]
        else:
            need[i] = max(0, b[i])
    for i in range(k):
        m = max(m, (need[i] + i) // (i + 1))
    print(sum(operations) + m)
main()