Overview

Given an array \(A\) of length \(N\), the problem asks to make all elements at least \(T\) by performing the minimum number of operations, where each operation selects \(K\) consecutive elements and adds \(+1\) to all of them. The minimum cost is the minimum number of operations multiplied by \(C\).

Analysis

Key Insight

When examining the flower beds from left to right, the only operations that can increase the value at position \(i\) are those with starting positions from \(i-K+1\) to \(i\). In particular, when processing from left to right, the only operation that includes position \(i\) and can still be newly started is the one with starting position \(i\) (operations starting at \(i+1\) or later do not include \(i\)).

Therefore, when scanning from left to right: - If the current moisture level is already \(T\) or more, do nothing. - If it is less than \(T\), then performing exactly \(T - \text{current value}\) operations starting at position \(i\) is mandatory (otherwise, position \(i\) can never be increased again).

This “forced” greedy approach holds, and the number of operations is automatically minimized.

Why the Naive Approach Is Too Slow

If we naively update all \(K\) elements in the array each time an operation is performed, each operation costs \(O(K)\). In cases where many operations are needed, the total becomes \(O(NK)\), which is far too slow for \(N \le 2\times 10^5\).

How to Solve It

We manage range additions using a difference array (imos method).

• As long as we know “how much has been cumulatively added to the current position,” the actual value of \(A_i\) can be computed as \(A_i + \text{add}\).
• If we perform \(need\) operations at position \(i\) (adding \(+need\) to the interval \([i, i+K-1]\)):
  • Add \(+need\) to the cumulative addition \(\text{add}\) from this point onward.
  • Since the effect expires \(K\) positions later, schedule “\(-need\)” at position \(i+K\).

This allows each position \(i\) to be processed in \(O(1)\), making the overall complexity \(O(N)\).

Algorithm

1. Prepare a difference array diff, and initialize the cumulative addition add = 0 and operation count ops = 0.
2. Process positions \(i = 0..N-1\) from left to right:
   • Update add += diff[i] to reflect scheduled adjustments (such as the expiration of addition effects).
   • The current moisture level is cur = A[i] + add.
   • If cur < T, the deficit need = T - cur is absolutely necessary:
     • ops += need (increase the operation count)
     • add += need (subsequent positions are immediately in a state where \(+need\) has been applied)
     • diff[i+K] -= need (schedule the effect to expire \(K\) positions ahead)
3. Output the minimum cost as ops * C.

(Example) With \(K=3\), if we perform \(need=5\) operations starting from \(i=2\), positions \(2, 3, 4\) each get \(+5\). Using the difference array, we record “from now on, \(+5\) is applied” with add += 5, and to cancel the effect at position \(5\), we set diff[5] -= 5.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (for the diff array)

Implementation Notes

• Since we access diff[i+K], it is safe to allocate diff with a length of at least \(N+K+1\).

• The operation count ops and ops * C can become very large, so using Python’s int (arbitrary precision) avoids overflow concerns (in other languages, 64-bit integers are required).

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

  Source Code

import sys

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

    diff = [0] * (N + K + 1)
    add = 0
    ops = 0

    for i in range(N):
        add += diff[i]
        cur = A[i] + add
        if cur < T:
            need = T - cur
            ops += need
            add += need
            diff[i + K] -= need

    print(ops * C)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.