Overview

This problem asks you to find the number of contiguous subarrays of length \(K\) within a sequence of length \(N\) whose sum is \(0\) or less.

Analysis

First, let’s consider a naive (brute-force) approach. For each starting position \(i\) (\(1 \leq i \leq N-K+1\)), we compute the sum of the \(K\) elements starting from that position and check whether it is \(0\) or less.

However, this method takes \(O(K)\) time to compute the sum of a single subarray. Since there are approximately \(N\) subarrays, the overall time complexity is \(O(N \times K)\). Given the constraints of this problem where \(N, K \leq 2 \times 10^5\), \(N \times K\) can reach up to \(4 \times 10^{10}\), which will not finish within the typical time limit (around 2 seconds).

Therefore, we focus on the key observation that “the sums of adjacent subarrays share most of their elements.”

For example, with \(N=5, K=3\) and sequence \(A = [A_1, A_2, A_3, A_4, A_5]\): 1. First subarray: \((A_1 + A_2 + A_3)\) 2. Next subarray: \((A_2 + A_3 + A_4)\)

Comparing these two, we can see that recomputing the common part \((A_2 + A_3)\) repeatedly is wasteful. The second sum can be obtained from the first sum by simply subtracting \(A_1\) and adding \(A_4\).

Algorithm

This technique is called the sliding window method.

1. First, compute the sum current_sum of the first subarray (from the \(1\)-st to the \(K\)-th element).
2. If current_sum is \(0\) or less, increment the count by \(+1\).
3. Next, slide the window one position to the right at a time.
   • Subtract the element leaving the window (left end) from current_sum.
   • Add the element entering the window (right end) to current_sum.
   • If the updated current_sum is \(0\) or less, increment the count by \(+1\).
4. Repeat this until the end.

With this method, each step requires only “one subtraction and one addition,” making it very efficient.

Complexity

• Time complexity: \(O(N)\)
  • Reading the data takes \(O(N)\), and the sliding window scan takes \(O(N)\), so the overall complexity is \(O(N)\). This is fast enough even when \(N=2 \times 10^5\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the input sequence.

Implementation Notes

• Data input: Since \(N\) and the values of \(A_i\) can be large, it is faster to read all input at once using something like sys.stdin.read().split() rather than calling Python’s input() multiple times.

• Updating the sum: You need to correctly specify the indices of the element entering and leaving the window, as in current_sum += a[i + k] - a[i].

• Initializing the count: Don’t forget to check the sum of the first \(K\) elements before the loop begins.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを取得し、空白で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N（データ数）とK（連続時間数）を取得します
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 各時間の品質指標を整数のリストとして取得します
    # map関数を使用することで、大量のデータを効率的に変換します
    a = list(map(int, input_data[2:]))
    
    # 最初のK時間の合計（最初のウィンドウ）を計算します
    current_sum = sum(a[:k])
    
    # 異常期間の個数をカウントする変数
    count = 0
    
    # 最初のウィンドウが異常期間（合計が0以下）であるか判定します
    if current_sum <= 0:
        count += 1
        
    # スライディングウィンドウを用いて、2番目以降のウィンドウの合計を効率的に計算します
    # i はウィンドウから外れる要素のインデックス、i + k は新しく入る要素のインデックスです
    for i in range(n - k):
        # 前の合計から外れる要素を引き、新しい要素を加えることで次の合計を求めます
        current_sum += a[i + k] - a[i]
        
        # 合計が0以下であれば異常期間としてカウントします
        if current_sum <= 0:
            count += 1
            
    # 結果を出力します
    print(count)

if __name__ == '__main__':
    solve()

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