Overview

Given flower beds arranged in a row, we want to bring the moisture level of each bed to at least a target value \(T\) by performing operations that water \(K\) consecutive beds at a time. The problem asks for the minimum cost required.

Analysis

For each flower bed \(i\), we compute the deficit \(d_i = \max(0, T - A_i)\) needed to reach the target value \(T\). The problem then reduces to minimizing the total number of operations, where each operation adds \(1\) to \(K\) consecutive elements in an interval.

A straightforward approach would be to scan from left to right and perform operations whenever a deficit is found. However, naively simulating this would require addition processing over the same interval multiple times within loops, resulting in a worst-case complexity of \(O(N^2)\), which is too slow for the constraint \(N \leq 2 \times 10^5\).

To address this, we use the imos method (difference array technique) to efficiently perform bulk additions over intervals. Specifically, we record \(+x\) at the starting position of an operation and \(-x\) at the position right after the ending position, and manage the current effect using a prefix sum approach.

In this way, we can efficiently track the “current amount of watering” at each position and perform only the necessary operations, processing everything in linear time.

Algorithm

1. Compute the required moisture for each flower bed: \(d_i = \max(0, T - A_i)\).
2. Scan from left to right, repeating the following:
   • Maintain the number of operations already applied to the current position, current_add, computed via difference array updates.
   • If the required moisture is not yet satisfied, perform enough operations to cover the deficit.
   • Since each operation applies to the interval \([i, i+K-1]\), record \(+\text{needed}\) at position \(i\) and \(-\text{needed}\) at position \(i+K\) in the difference array operations.
3. Multiply the total number of operations total_ops by the cost \(C\) and output the result.

This algorithm greedily determines the required number of operations from left to right while efficiently handling interval updates.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Setting the size of the difference array operations to \(N+1\) helps prevent out-of-bounds access.

• current_add is updated like a prefix sum of the difference array, allowing us to quickly obtain the number of operations applied to the current position.

• The final cost is the total number of operations total_ops multiplied by \(C\).

  Source Code

import sys
from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    T = int(data[2])
    C = int(data[3])
    A = list(map(int, data[4:]))
    
    # 各花壇が必要とする追加水分量
    diff = [max(0, T - a) for a in A]
    
    # 累積和を使って効率的に範囲和を計算
    # 各位置で必要な最小操作回数をシミュレーション
    
    # 差分配列を使って操作の影響を管理
    # 操作は連続K個に+1するので、差分更新が有効
    
    # 最小コストを求める
    # 貪欲法：左から順に、必要ならその位置からK個に操作を行う
    
    operations = [0] * (N + 1)  # 差分用の配列、N+1にすることで範囲外アクセス防止
    total_ops = 0
    current_add = 0  # 現在の位置に適用されている操作の合計
    
    for i in range(N):
        current_add += operations[i]
        needed = diff[i] - current_add
        if needed > 0:
            total_ops += needed
            current_add += needed
            if i + K <= N:
                operations[i + K] -= needed
                
    print(total_ops * C)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.