Overview

This problem asks you to determine whether you can make each plot’s water level exactly match the target value by repeatedly performing an operation that waters \(K\) consecutive plots simultaneously.

Analysis

Key Insight

The key point of this problem is that when examining from left to right, the “number of watering operations” at each position is uniquely determined.

Let’s consider a concrete example. For \(N=5, K=3\), with target values \([2, 3, 4, 2, 1]\):

• To make plot 0’s water level \(2\), we need to water 2 times starting from position 0
• Plot 1 is affected by the watering from position 0 (2 times). Since the target is 3, we water 1 additional time from position 1
• In this way, we determine the required number of operations sequentially from left to right

Problem with the Naive Approach

If we sum up all the watering counts that affect each plot every time we calculate the water level, the worst-case time complexity becomes \(O(NK)\), resulting in TLE.

Solution

We use a sliding window. The waterings that affect plot \(i\) are the \(K\) operations from position \(\max(0, i-K+1)\) to position \(i\). Since this is a contiguous interval, each time we move to the next plot: - Add the newly included watering count - Subtract the watering count that leaves the interval

This allows us to calculate each plot’s water level in \(O(1)\).

Conditions for Impossibility

1. Already exceeded the target: When the current water level is greater than the target value (we cannot remove water)
2. Cannot adjust: We can only water with position \(i\) as the left endpoint when \(i + K - 1 < N\) (i.e., \(i \leq N - K\)). After that point, we cannot add new waterings, so if the water level doesn’t match the target, it’s impossible

Algorithm

1. Maintain array \(water[i]\) = number of times to water with position \(i\) as the left endpoint
2. \(current\_sum\) = total watering count affecting the current plot (sliding window)
3. Process each plot \(i\) from left to right:
   • \(needed = T[i] - current\_sum\) (additional water amount needed)
   • If \(needed < 0\), output No (already exceeded)
   • If \(i \leq N - K\), set \(water[i] = needed\) and add to \(current\_sum\)
   • If \(i > N - K\) and \(needed \neq 0\), output No (cannot adjust)
   • Subtract \(water[i-K+1]\) that leaves the window from \(current\_sum\)
4. If all plots are processed successfully, output Yes

Complexity

• Time complexity: \(O(N)\) — each plot is processed once
• Space complexity: \(O(N)\) — storing array \(water\) and input array \(T\)

Implementation Notes

• Pay attention to the timing of sliding window updates. Before moving to plot \(i+1\), remove the effect of position \(i-K+1\)
• We can only water with position \(i\) as the left endpoint when \(i \leq N - K\). Handling boundary conditions accurately is important
• The case where \(needed\) becomes negative means the water level was exceeded by previous waterings, so return No immediately

Source Code

def solve():
    N, K = map(int, input().split())
    T = list(map(int, input().split()))
    
    # Determine the watering count at each position
    # water[i] = number of times to water with position i as the left endpoint
    # Water level at position i = sum(water[max(0, i-K+1):i+1])
    
    # Track the current water level using an imos-like approach
    # current_water = water level given to the current plot
    
    # When determining water[i], the water level of plot i is determined by
    # water[i-K+1] + water[i-K+2] + ... + water[i]
    # Looking from plot 0 onwards, when we look at plot i, we can determine water[i]
    
    water = [0] * N  # water[i] = number of times to water with position i as the left endpoint
    current_sum = 0  # total of waterings affecting the current plot
    
    for i in range(N):
        # The water level for plot i is the sum of watering counts from position max(0, i-K+1) to i
        # current_sum contains that total (sliding window)
        
        # The target water level for plot i is T[i]
        # The current water level is current_sum
        # The additional water amount needed is T[i] - current_sum
        # We satisfy this with water[i] (watering with position i as the left endpoint)
        
        needed = T[i] - current_sum
        
        if needed < 0:
            # Already exceeded the target
            print("No")
            return
        
        # Set the number of times to water with position i as the left endpoint
        # However, we can only use position i as the left endpoint when i + K - 1 < N, i.e., i <= N - K
        if i <= N - K:
            water[i] = needed
            current_sum += needed
        else:
            # Cannot water with position i as the left endpoint
            # So current_sum must be exactly T[i]
            if needed != 0:
                print("No")
                return
        
        # Before moving to the next plot, subtract the part that leaves the window
        # Plot i+1 is affected by positions max(0, i+1-K+1) to i+1
        # Plot i was affected by positions max(0, i-K+1) to i
        # Position i-K+1 leaves the window
        if i - K + 1 >= 0:
            current_sum -= water[i - K + 1]
    
    print("Yes")

solve()

---

This editorial was generated by claude4.5opus.