Overview

Find the number of intervals where the sum of \(K\) consecutive elements is \(0\) or less.

Discussion

A naive approach for this problem would be to compute and check the sum for every interval. However, such a brute-force search is impractical because there are at most \(N - K + 1\) intervals, and computing the sum of each interval takes \(O(K)\), resulting in an overall time complexity of \(O(NK)\). Given the constraints \(N, K \sim 2 \times 10^5\), this would result in TLE.

Therefore, to efficiently compute the sums of consecutive subsequences, we use the “prefix sum” or “sliding window” technique.

Specifically, after computing the sum of the first interval, when moving to the next interval, we subtract the element that is leaving and add the new element to update the sum. This allows us to compute the sum of each interval in \(O(1)\), bringing the overall time complexity down to \(O(N)\).

For example, given the input A = [1, -3, 2, -1, 0] with \(K = 3\): - First interval: \(1 + (-3) + 2 = 0\) → abnormal period - Next interval: \((-3) + 2 + (-1) = -2\) → abnormal period - Last interval: \(2 + (-1) + 0 = 1\) → normal

In this way, we efficiently update the sum while counting the number of intervals that satisfy the condition.

Algorithm

1. Compute the sum of the first \(K\) elements, and increment the count if it is \(0\) or less.
2. Then, slide the interval one position at a time while updating the sum:
   • Newly added element: \(A[i]\)
   • Removed element: \(A[i - K]\)
3. At each step, check whether the sum is \(0\) or less, and increment the count if the condition is satisfied.
4. Output the final count.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding the input array)

Implementation Notes

• The key point is to compute the sum of the first interval only once using sum(A[:K]).

• The sum update within the loop is performed as current_sum += A[i] - A[i - K].

• The interval starting position begins at \(i = K\) and the loop continues while \(i < N\).

  Source Code

N, K = map(int, input().split())
A = list(map(int, input().split()))

count = 0
current_sum = sum(A[:K])
if current_sum <= 0:
    count += 1

for i in range(K, N):
    current_sum += A[i] - A[i - K]
    if current_sum <= 0:
        count += 1

print(count)

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