Overview

This is a problem where you have \(N\) flower beds arranged in a row, and you need to find the minimum cost to make all of them have moisture levels of at least \(T\), by repeatedly performing an operation that adds to \(K\) consecutive flower beds (at a cost of \(C\) each).

Analysis

Applying a Greedy Approach

In this problem, a greedy approach that checks from the leftmost flower bed whether each one “meets the target value \(T\)” is effective.

When the moisture level of some flower bed \(j\) is less than \(T\), we must perform some operation to increase the moisture of the \(j\)-th flower bed. At this point, by choosing the operation range (of length \(K\)) as far to the right as possible, we can simultaneously increase the moisture of flower beds to the right that haven’t been checked yet, minimizing the number of operations needed in the future.

Specifically, the starting position \(i\) of an operation that covers flower bed \(j\) must satisfy \(j-K+1 \leq i \leq j\), but to maximize the benefit to flower beds on the right, it is optimal to choose the largest possible \(i\).

Efficient Range Addition Management

If we naively simulate “adding \(1\) to each of the \(K\) elements in the range,” this takes \(O(NK)\) time in the worst case, which is too slow for the constraints (\(N=2 \times 10^5\)). Therefore, we use a sliding window (or difference array concept) to compute the total number of operations affecting the current flower bed in \(O(1)\) time.

1. We maintain a variable current_window_sum that holds the total number of operations covering the flower bed we are currently examining.
2. When moving to the right, we subtract the count of old operations that have fallen out of range from current_window_sum.
3. When performing a new operation, we add its count to current_window_sum and record where the operation started.

Algorithm

1. Initialize the necessary variables:
   • x[i]: the number of operations that started with flower bed \(i\) as the left endpoint
   • current_window_sum: the cumulative number of operations covering the current flower bed
   • total_ops: the total number of operations overall
2. Scan flower beds from \(j = 1\) to \(N\) in order:
   • If \(j - K \geq 1\), operations that started at flower bed \(j-K\) no longer cover flower bed \(j\), so subtract x[j-K] from current_window_sum.
   • Calculate the current moisture of flower bed \(j\): \(A_j + \text{current\_window\_sum}\)
   • If there is a deficit needed relative to the target \(T\):
     • Determine the operation’s starting position start_idx. Normally this is \(j\), but if it would exceed the right end, set it to \(N-K+1\).
     • Add needed to both total_ops and current_window_sum.
     • Record needed in x[start_idx].
3. Output total_ops * C as the final answer.

Complexity

• Time complexity: \(O(N)\)
  • We only scan the flower beds once from left to right, and each step takes constant time.
• Space complexity: \(O(N)\)
  • We use \(O(N)\) memory for the initial moisture array \(A\) and the array \(x\) recording the number of operations started at each position.

Implementation Notes

• Restriction on sprinkler placement position: Just because flower bed \(j\) has a deficit doesn’t mean we can always set start_idx = j. Since the right end of the sprinkler must not exceed \(N\), the starting position is limited to at most \(N-K+1\).

• Handling large values: Since \(T, A_i, C\) can be as large as \(10^9\), note that the answer may require 64-bit integers (in Python this is handled automatically).

• Fast I/O: Since \(N\) can be large, reading all input at once using sys.stdin.read().split() can reduce execution time.

  Source Code

import sys

def solve():
    # 使用するメモリや実行速度を最適化するために、sys.stdin.read().split() を用いて
    # 入力データを一括で読み込み、トークンに分割します。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # 問題文から与えられるパラメータをパースします。
    # N: 花壇の個数
    # K: スプリンクラーが一度に水をまく範囲
    # T: 目標とする土の水分量
    # C: スプリンクラー1回あたりの水道代
    N = int(input_data[0])
    K = int(input_data[1])
    T = int(input_data[2])
    C = int(input_data[3])
    
    # 各花壇の初期水分量 A_i
    A = list(map(int, input_data[4:]))
    
    # x[i] は、i番目の花壇を始点としてスプリンクラーを作動させた回数を記録します。
    # インデックスを1から始めるためにサイズを N + 1 とします。
    # スプリンクラーの始点として選べる最大のインデックスは N - K + 1 です。
    x = [0] * (N + 1)
    
    # current_window_sum は、現在注目している花壇 j をカバーしている
    # スプリンクラーによる水分上昇量の合計を保持します。
    current_window_sum = 0
    
    # total_ops は、すべての花壇を目標値以上にするために必要な総操作回数です。
    total_ops = 0
    
    # スプリンクラーを作動させることができる右端の開始位置
    limit = N - K + 1
    
    # 左側の花壇から順に、目標水分量 T に達しているか確認していきます。
    for j in range(1, N + 1):
        # スプリンクラーを i 番目から i + K - 1 番目まで作動させたとき、
        # 花壇 j がその範囲外（j < i または j > i + K - 1）になるとき、
        # その操作による水分上昇効果を除外します。
        # ここでは左から右へ進んでいるため、i = j - K の操作が j をカバーしなくなるタイミングです。
        if j - K >= 1:
            # 操作の始点 i は必ず limit 以下であるため、その範囲内であれば減算します。
            if j - K <= limit:
                current_window_sum -= x[j - K]
        
        # 現在の花壇 j の水分量は、初期値 A[j-1] にこれまでの操作による増加分を加えたものです。
        # 目標 T に達するために不足している水分量 needed を計算します。
        needed = T - A[j - 1] - current_window_sum
        
        if needed > 0:
            # 水分が不足している場合、スプリンクラーを作動させます。
            # 貪欲法（Greedy）の考え方に基づき、現在の花壇 j をカバーしつつ、
            # できるだけ右側の花壇にも効果が及ぶように、可能な限り右側の位置を始点として選びます。
            # その始点は、現在の位置 j と、可能な右端 limit のうちの小さい方になります。
            start_idx = j if j < limit else limit
            
            # 不足分を補うために needed 回の操作を行います。
            x[start_idx] += needed
            total_ops += needed
            
            # 新しく追加した操作は、現在の花壇 j もカバーするため、ウィンドウの合計に加算します。
            current_window_sum += needed
            
    # すべての花壇を T 以上にするために必要な最小コスト（総操作回数 × 1回あたりのコスト）を出力します。
    print(total_ops * C)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.