Overview

This problem asks you to find the number of contiguous subsequences of a sequence that have length at least \(K\) and a sum of elements at most \(\lfloor T/C \rfloor\).

Analysis

First, the reading time condition \(C \times (A_l + \cdots + A_r) \le T\) can be rewritten as \(A_l + \cdots + A_r \le \lfloor T/C \rfloor\) by dividing both sides by \(C\).

The key insight in this problem is that the number of pages per day \(A_i\) is always at least \(1\). This guarantees the property that “the longer the interval, the larger the total number of pages always becomes (monotonically increasing).”

If we brute-force all combinations of intervals \((l, r)\), the number of states becomes \(O(N^2)\), which will exceed the time limit (TLE) given the constraint \(N \le 2 \times 10^6\). However, by utilizing the “monotonicity” mentioned above, when we find the furthest right endpoint \(r\) that satisfies the condition for a given left endpoint \(l\), we know that all shorter intervals also satisfy the condition. Furthermore, when we shift the left endpoint \(l\) to the right, the total decreases, so the right endpoint \(r\) can be moved further to the right (or stay at the same position) from its previous location. In this way, by using the “Two Pointers” technique, where both endpoints only move in one direction, we can significantly reduce the computational complexity.

Algorithm

1. Compute the upper limit of the allowed total pages \(M = \lfloor T/C \rfloor\).
2. Using the two pointers technique, examine the left endpoint \(l\) sequentially from \(0\) to \(N-1\).
3. As long as adding the next element \(A_r\) to the sum current_sum of the current interval \([l, r)\) (from the \(l\)-th to the \((r-1)\)-th element) does not exceed \(M\), advance the right endpoint \(r\) to the right.
4. When \(r\) has been advanced as far as possible, the maximum interval satisfying the condition is \([l, r)\). At this point, let \(x\) (\(l \le x < r\)) be the right endpoint index needed to make the length at least \(K\). From the interval length \(x - l + 1 \ge K\), we need \(x \ge l + K - 1\). The range of \(x\) satisfying the condition is \(l + K - 1 \le x \le r - 1\), so the count is \((r - 1) - (l + K - 1) + 1 = r - l - K + 1\). Add this to the answer.
5. In preparation for moving to the next \(l\), subtract \(A_l\) from current_sum. However, if \(r = l\) (for example, because \(A_l > M\)), there is no element to subtract, so we simply advance \(r\) by one.

Complexity

• Time complexity: \(O(N)\) The left endpoint \(l\) increases by \(1\) from \(0\) to \(N-1\), and the right endpoint \(r\) also only increases in one direction from \(0\) up to at most \(N\). Therefore, the inner while loop executes at most \(N\) times in total across the entire algorithm, giving an overall complexity of \(O(N)\).
• Space complexity: \(O(N)\) Since we store the sequence \(A\) of length \(N\) as an array in memory, it consumes \(O(N)\) space.

Implementation Notes

• Use of integer division: If \(T / C\) is computed as a floating-point number (decimal), precision errors may occur when the values are very large, potentially leading to incorrect judgments. In Python, always use the // operator to perform exact floor integer division.

• Corner case in the two pointers technique: When \(A_l > M\), no elements can be included in the interval, resulting in \(r = l\). If you subtract \(A_l\) from current_sum in this case, the total becomes negative and subsequent calculations will be incorrect. Therefore, it is important not to forget to include the if r == l: branch that forcibly advances only \(r\).

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    C = int(input_data[1])
    T = int(input_data[2])
    K = int(input_data[3])
    
    M = T // C
    
    A = list(map(int, input_data[4:]))
    
    ans = 0
    r = 0
    current_sum = 0
    
    for l in range(N):
        while r < N and current_sum + A[r] <= M:
            current_sum += A[r]
            r += 1
        
        if r - l >= K:
            ans += r - l - K + 1
            
        if r == l:
            r += 1
        else:
            current_sum -= A[l]
            
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.