Overview

This problem asks us to determine whether, given a sequence \(T\) of length \(N\), we can perfectly reproduce \(T\) from the initial state (all zeros) by repeatedly performing the operation of adding \(1\) to an interval of length \(K\).

Analysis

At first glance, it seems difficult to decide which intervals to water and how many times, but let’s focus on the key observation that by examining sections from the leftmost one in order, the number of sprinkler activations that should start at each position is uniquely determined.

Key Observation

The moisture level \(T_i\) of the \(i\)-th section is the total number of sprinkler operations that cover that section. Let \(x_i\) denote the number of times a sprinkler starting at section \(i\) is activated. Since a sprinkler waters \(K\) consecutive sections, the operations that affect section \(i\) are \(x_{i-K+1}, x_{i-K+2}, \ldots, x_i\).

1. For section 1: The only sprinkler that can cover section 1 is the one starting at index 1. Therefore, \(x_1 = T_1\) is determined.
2. For section \(j \le K\): The sprinklers covering section \(j\) are \(x_1, x_2, \ldots, x_j\). \(T_j = x_1 + x_2 + \dots + x_j\) \(T_{j-1} = x_1 + x_2 + \dots + x_{j-1}\) Taking the difference gives \(x_j = T_j - T_{j-1}\).
3. For section \(j > K\): The sprinklers covering section \(j\) are \(x_{j-K+1}, \ldots, x_j\). \(T_j = x_{j-K+1} + \dots + x_j\) \(T_{j-1} = x_{j-K} + \dots + x_{j-1}\) Taking the difference gives \(T_j - T_{j-1} = x_j - x_{j-K}\), which rearranges to \(x_j = T_j - T_{j-1} + x_{j-K}\).

Key Points for Judgment

• Non-negative integers: The number of sprinkler activations \(x_i\) must be a non-negative integer. If \(x_i < 0\) is computed at any point, we can immediately output No.
• Consistency beyond the valid range: Sprinklers can only start up to the \((N-K+1)\)-th section. For sections beyond that (\(j > N-K+1\)), no new sprinkler can be started, so we need to verify that the existing \(x\) values alone satisfy the target moisture level \(T_j\).

Algorithm

1. Prepare an array \(x\) of length \(N-K+1\) (initialized to \(0\)).
2. Loop from \(j = 1\) to \(N\) in order.
3. When \(j \le N-K+1\) (a new sprinkler can be started):
   • If \(j \le K\), then \(x_j = T_j - T_{j-1}\)
   • If \(j > K\), then \(x_j = T_j - T_{j-1} + x_{j-K}\)
   • If \(x_j < 0\), output No and terminate.
4. When \(j > N-K+1\) (no new sprinkler can be started):
   • If \(j \le K\), check whether \(T_j = T_{j-1}\).
   • If \(j > K\), check whether \(T_j = T_{j-1} - x_{j-K}\).
   • If there is a contradiction, output No and terminate.
5. If no contradictions are found through the end, output Yes.

Complexity

• Time complexity: \(O(N)\)
  • We only scan the sequence once, making it very fast.
• Space complexity: \(O(N)\)
  • Memory is needed for the input array \(T\) and the array \(x\) recording the number of operations.

Implementation Notes

• Index handling: In the formulas we used \(1\)-indexed notation, but in the program it becomes \(0\)-indexed, so be careful about index shifts such as T[j-1] and x[j-K-1].

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), in Python it is advisable to read all input at once using techniques like sys.stdin.read().split().

  Source Code

import sys

def solve():
    # Read all input at once for efficient processing
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    # T represents the target moisture levels for each of the N sections
    T = list(map(int, input_data[2:]))
    
    # x[i] will store the number of times a sprinkler is used starting at index i.
    # There are N-K+1 possible starting positions for the sprinkler.
    x = [0] * (N - K + 1)
    
    for j in range(1, N + 1):
        # Target moisture for the current section (1-indexed j)
        t_curr = T[j-1]
        t_prev = T[j-2] if j > 1 else 0
        
        if j <= N - K + 1:
            # For sections where a new sprinkler can start
            if j <= K:
                # When j <= K, the moisture at j is the sum of all sprinklers starting at 1...j
                # T_j = x_1 + ... + x_j
                # T_{j-1} = x_1 + ... + x_{j-1}
                # Therefore, x_j = T_j - T_{j-1}
                x[j-1] = t_curr - t_prev
            else:
                # When j > K, the moisture at j is the sum of sprinklers starting at j-K+1...j
                # T_j = x_{j-K+1} + ... + x_j
                # T_{j-1} = x_{j-K} + ... + x_{j-1}
                # T_j - T_{j-1} = x_j - x_{j-K}
                # Therefore, x_j = T_j - T_{j-1} + x_{j-K}
                x[j-1] = t_curr - t_prev + x[j-K-1]
            
            # The number of times a sprinkler is used must be a non-negative integer.
            # If x[j-1] is negative, it's impossible to reach the target exactly.
            if x[j-1] < 0:
                print("No")
                return
        else:
            # For sections where no new sprinkler can start (j > N-K+1)
            # We check if the moisture level matches the target.
            if j <= K:
                # If j <= K and j > N-K+1, the moisture is the sum of all available sprinklers.
                # The moisture level should not change from the previous section.
                if t_curr != t_prev:
                    print("No")
                    return
            else:
                # If j > K and j > N-K+1, the moisture at j is the sum of x_{j-K+1}...x_{N-K+1}.
                # The change in moisture from the previous section must be -x_{j-K}.
                if t_curr != t_prev - x[j-K-1]:
                    print("No")
                    return
                    
    # If all sections match their target moisture levels exactly, output Yes.
    print("Yes")

if __name__ == '__main__':
    solve()

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