Overview

This is a problem where, for each contiguous subarray of length \(K\) (a sliding window), we count the number of subarrays whose element sum is at most \(0\).

Analysis

For each starting position \(i\) (\(1 \le i \le N-K+1\)), we can find the answer by computing the sum of the subarray \(A_i, A_{i+1}, \ldots, A_{i+K-1}\).

However, if we naively “sum \(K\) elements each time for every subarray,” there are \(N-K+1\) subarrays and each requires \(K\) additions, resulting in a total of \(O(NK)\) operations.
Since the constraints allow up to \(N=2\times10^5\), if \(K\) is of similar magnitude, \(O(NK)\) will not finish within a realistic time limit (causing TLE).

The key observation here is that adjacent subarrays of length \(K\) share almost all the same elements.
For example:

• 1st subarray: \(A_1 + A_2 + \cdots + A_K\)
• 2nd subarray: \(A_2 + A_3 + \cdots + A_{K+1}\)

The difference between these two is simply “\(A_1\) is removed and \(A_{K+1}\) is added,” so:

\[ \text{sum}_{2} = \text{sum}_{1} - A_1 + A_{K+1} \]

This can be updated in constant time, bringing the overall complexity down to \(O(N)\).

Algorithm

We solve this using a sliding window (window update technique).

1. First, compute the sum \(s\) of the initial subarray \(A_1 \sim A_K\).
2. If \(s \le 0\), add 1 to the answer.
3. Advance the right end of the window one step at a time (for \(i = K\) to \(N-1\)), updating the sum as follows:
   • Element entering the window: \(A_i\)
   • Element leaving the window: \(A_{i-K}\)
   • Update: \(s \leftarrow s + A_i - A_{i-K}\)
4. Each time the updated \(s \le 0\), increment the answer.
5. Output the final count.

(Example) \(A=[2, -5, 1, 1], K=2\)
Initial: \(2+(-5)=-3 \le 0\) → 1 subarray
Next: \(-3 + 1 - 2 = -4 \le 0\) → 2 subarrays
Next: \(-4 + 1 - (-5) = 2\) → no increment
The answer is 2.

Complexity

• Time complexity: \(O(N)\) (each element is processed at most once for “entering” and “leaving”)
• Space complexity: \(O(1)\) (only a running sum and a counter are needed; additional space beyond the input array)

Implementation Notes

• It is clean to first compute the initial window sum sum(A[:K]), then update with s += A[i] - A[i-K] for subsequent windows.

• The condition is “at most \(0\),” so the check should be s <= 0 (be careful not to mistakenly use < 0).

• Since \(N\) can be large, using sys.stdin.readline for input ensures stable performance.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    s = sum(A[:K])
    ans = 1 if s <= 0 else 0
    
    for i in range(K, N):
        s += A[i] - A[i - K]
        if s <= 0:
            ans += 1
    
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.