Overview

This is a problem where you need to determine whether it’s possible to make each section’s moisture level exactly match the target value using a sprinkler that can water \(K\) consecutive sections simultaneously.

Approach

In this problem, rather than directly simulating how many times to use the sprinkler, we need the perspective of “how should we distribute the watering so that each section’s moisture level matches the target value?”

The key insight is that the sprinkler operation adds the same amount of moisture to \(K\) consecutive sections. In other words, it is efficient to think about the “distribution of operation counts” needed to achieve the final moisture level for each section.

Thinking in Terms of Differences

For example, when the target moisture array is \(T = [2, 3, 3, 2]\), we can determine the answer by working backwards to figure out how many operations were “first applied” to each section after using the sprinkler some number of times.

However, a naive simulation would require recording and accumulating operation counts for each section, potentially requiring up to around \(10^9\) operations, which is infeasible time-wise (TLE).

Therefore, the standard technique is to use the inverse of prefix sums, namely differences.

What is a Difference Array?

An array of differences between adjacent elements of array \(T\): $\( \text{diff}[i] = \begin{cases} T[0] & (i = 0) \\ T[i] - T[i-1] & (i > 0) \end{cases} \)$

Using this difference array, we can efficiently represent the effect range of operations (\(K\) consecutive sections).

This is because using the sprinkler on the interval \([l, l+K-1]\) corresponds to the following changes in the difference array: - Add \(+1\) to \(\text{diff}[l]\) - Add \(-1\) to \(\text{diff}[l+K]\)

In other words, a range addition can be expressed as updates at just two points.

Therefore, we need to determine whether the difference array corresponding to the target moisture levels can be constructed from non-negative operation counts.

Specifically, we check the following conditions:

1. The first \(K-1\) differences are non-negative (because we cannot start an operation on an interval of fewer than \(K\) sections from the left end).
2. For differences from the \(K\)-th onward, \(\text{diff}[i] = \text{diff}[i-K] + (T[i] - T[i-1])\) is always non-negative (because operations propagate from previous intervals).
3. The last \(K-1\) differences are all zero (because we cannot start an operation beyond that point to the right).

Algorithm

1. Create the difference array \(\text{diff}\) from the target moisture array \(T\).
2. Confirm that the first \(K-1\) terms of \(\text{diff}\) are all non-negative.
3. For the \(K\)-th term onward, update as \(\text{diff}[i] = \text{diff}[i] + \text{diff}[i - K]\) to reflect operation propagation, and check that each value is non-negative.
4. Confirm that the last \(K-1\) terms are all zero.
5. If all conditions are satisfied, output Yes; otherwise, output No.

Complexity

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

Implementation Notes

• Setting the difference array size to \(N+1\) allows the subtraction at \(\text{diff}[i+K]\) to be handled safely.

• Don’t forget to check the last \(K-1\) terms.

• In Python, it is recommended to use fast input processing (such as sys.stdin.read).

  Source Code

import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    T = list(map(int, data[2:]))

    # 差分の配列を作成
    diff = [0] * (N + 1)
    diff[0] = T[0]
    for i in range(1, N):
        diff[i] = T[i] - T[i-1]
    
    # 最初のK-1個の差分が非負であることを確認
    for i in range(K-1):
        if diff[i] < 0:
            print("No")
            return
    
    # K番目以降の差分をチェック
    for i in range(K, N):
        diff[i] += diff[i - K]
        if diff[i] < 0:
            print("No")
            return
    
    # 最後のK-1個の差分がゼロであることを確認
    for i in range(N - K + 1, N):
        if diff[i] != 0:
            print("No")
            return

    print("Yes")

if __name__ == "__main__":
    main()

---

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