Overview

We can only “increase” the number of flowers in each flower bed to achieve \(B_i \ge A_i\), such that all adjacent differences satisfy \(|B_i-B_{i+1}| \le K\). We want to find the minimum total number of additional flowers \(\sum(B_i-A_i)\).

Analysis

Key Insight: The constraint creates a “lower bound from every point”

The condition \(|B_i-B_{i+1}| \le K\) implies not only for adjacent pairs, but also for distant pairs \(i,j\): [ |B_i-B_j| \le K|i-j| ] (This follows by summing up the adjacent inequalities.)

Then for any \(i,j\): [ B_i \ge B_j - K|i-j| \ge A_j - K|i-j| ] Therefore, in any beautiful state, the following must hold: [ B_i \ge \max_j (A_j - K|i-j|) ]

Define: [ C_i := \max_j (A_j - K|i-j|) ] This collects the “absolutely necessary lower bound” at each \(i\).

Does \(C_i\) itself form a beautiful state?

For each \(j\), the function \(f_j(i)=A_j-K|i-j|\) changes by at most \(K\) when \(i\) moves by 1 (it is \(K\)-Lipschitz).
And the maximum of \(K\)-Lipschitz functions is also \(K\)-Lipschitz, so \(C_i=\max_j f_j(i)\) satisfies: [ |Ci-C{i+1}| \le K ] Furthermore, by taking \(j=i\), we get \(C_i \ge A_i\).

This means \(C\) satisfies the “beautiful state” conditions, and for every valid solution \(B\), we have \(B_i \ge C_i\). Therefore, \(C\) is the minimum at each \(i\), and consequently the total number of additional flowers is also minimized.

Why the naive approach is too slow

Computing \(C_i=\max_j(A_j-K|i-j|)\) directly requires examining all \(j\) for each \(i\), resulting in \(O(N^2)\) time, which is too slow for \(N \le 2\times 10^5\).

Instead, we split this maximum into left and right contributions and compute it in \(O(N)\).

Algorithm

We want to compute: [ C_i=\max_j(A_j-K|i-j|) ] We split into \(j \le i\) and \(j \ge i\).

1) Contribution from the left (\(j \le i\))

[ A_j-K(i-j)= (Aj+Kj)-Ki ] Therefore: [ \max{j\le i}(Aj-K(i-j)) = \left(\max{j\le i}(A_j+Kj)\right)-Ki ] So we just need the prefix maximum of \(A_j+Kj\).

In code: - pref[i] = max_{j<=i}(A[j] + K*j) - Lower bound from the left: c_left = pref[i] - K*i

2) Contribution from the right (\(j \ge i\))

[ A_j-K(j-i)= (Aj-Kj)+Ki ] Therefore: [ \max{j\ge i}(Aj-K(j-i)) = \left(\max{j\ge i}(A_j-Kj)\right)+Ki ] So we just need the suffix maximum of \(A_j-Kj\).

In code: - suf[i] = max_{j>=i}(A[j] - K*j) - Lower bound from the right: c_right = suf[i] + K*i

3) Combine to form \(C_i\)

[ Ci = \max(c_left, c_right) ] Finally, the answer is: [ \sum{i=1}^N (C_i - A_i) ] (\(C_i \ge A_i\) is guaranteed.)

Complexity

• Time complexity: \(O(N)\) (two scans for prefix/suffix + aggregation)
• Space complexity: \(O(N)\) (pref, suf arrays)

Implementation Notes

• Since \(A_i, K, N\) can be large, values can reach approximately \(10^9 + 10^9\cdot 2\times10^5\). This is fine in Python, but in other languages, 64-bit integers are required.

• The trick is to precompute the cumulative maximum of A[i] + K*i / A[i] - K*i so that we can express the bounds as pref[i] - K*i and suf[i] + K*i.

• Since the input can be large, we use sys.stdin.buffer.read() for fast input reading.

  Source Code

import sys

def main():
    it = map(int, sys.stdin.buffer.read().split())
    N = next(it)
    K = next(it)
    A = [next(it) for _ in range(N)]

    pref = [0] * N
    best = -10**30
    for i, a in enumerate(A):
        v = a + K * i
        if v > best:
            best = v
        pref[i] = best

    suf = [0] * N
    best = -10**30
    for i in range(N - 1, -1, -1):
        v = A[i] - K * i
        if v > best:
            best = v
        suf[i] = best

    ans = 0
    for i, a in enumerate(A):
        c = pref[i] - K * i
        t = suf[i] + K * i
        if t > c:
            c = t
        ans += c - a

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.