Overview

We determine whether an array of length \(N\) can be made to exactly match target values \(T_i\) (without any element exceeding its target) using only operations that add \(+1\) to a contiguous subarray of length \(K\).

Analysis

Since this operation is an “range addition,” naively “updating \(K\) elements for each operation” would result in \(O(\text{operations}\times K)\) complexity, which is too slow when the number of operations is large (\(T_i\) can be up to \(10^9\)).

The two key observations are:

1. When scanning from left to right, the last opportunity to increase the value at position \(i\) is determined
   The starting positions of length-\(K\) subarrays that include position \(i\) range from \(i-K+1\) to \(i\), but valid starting positions within the array are \(1\) to \(N-K+1\).
   Therefore, while \(i \le N-K+1\), we can decide “how many operations to start here,” but for \(i > N-K+1\) (the last \(K-1\) positions), no new operations can be started, so if the current water amount doesn’t match the target at that point, it’s impossible.

2. Greedily “starting exactly the deficit amount at the current position” is optimal
   Scanning from left, let \(cur\) be the current water amount at position \(i\):

   • If \(cur > T_i\), we’ve already exceeded the target, and there’s no way to decrease, so immediately output No
   • If \(cur < T_i\), we can still increase position \(i\) (including by starting an operation at position \(i\)), so start exactly \(T_i - cur\) operations beginning at position \(i\)
     This way, position \(i\) will exactly equal \(T_i\), leaving no unresolved impact on future decisions.

The challenge is “efficiently maintaining the current water amount \(cur\),” but range additions can be handled with a difference array (imos method) for \(O(1)\) updates and \(O(1)\) lookups.

Algorithm

We use a difference array diff to track “the cumulative addition that previously started operations contribute to the current position.”

• Let cur be “the water amount when we reach position \(i\)”
• For each \(i=1..N\):
  1. cur += diff[i] (reflect the start/end effects of past operations)
  2. If \(i \le N-K+1\) (we can still start an operation here):
     • need = T[i] - cur
     • If need < 0, the target is exceeded, so output No
     • If need > 0, water \([i, i+K-1]\) exactly need times.
       This is represented as:

          - `cur += need` (immediately reflect the effect at position $i$)
          - `diff[i+K] -= need` (the effect disappears from position $i+K$ onward)
       

  3. If \(i > N-K+1\) (no more operations can be started):
     • If cur != T[i], adjustment is impossible, so output No

If no contradiction is found by the end, output Yes.

(Example) For \(N=5, K=3, T=[1,2,2,1,0]\), we start 1 operation at \(i=1\), and so on, filling in deficits from left to right, and at the tail end we only perform equality checks.

Complexity

• Time complexity: \(O(N)\) (each position is processed exactly once)
• Space complexity: \(O(N)\) (for the difference array diff)

Implementation Notes

• The key point is to split at last_start = N-K+1, separating the “range where operations can be started” from the “range where only equality checks can be performed.”

• For the difference array, we only write to diff[i+K] -= need, the end position (where the effect disappears), since the start is directly added to cur.

• Since i+K can appear as an index in diff, we allocate the array with a margin of about N+K+5.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    T = [0] + list(map(int, input().split()))

    diff = [0] * (N + K + 5)
    cur = 0

    last_start = N - K + 1
    for i in range(1, N + 1):
        cur += diff[i]
        if i <= last_start:
            need = T[i] - cur
            if need < 0:
                print("No")
                return
            cur += need
            diff[i + K] -= need
        else:
            if cur != T[i]:
                print("No")
                return

    print("Yes")

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.