Overview

This problem asks us to find the number of contiguous subsequences (intervals) of length \(K\) or more from a sequence \(A\) of length \(N\), such that the sum of the elements multiplied by \(C\) is at most \(T\).

Analysis

Simplifying the Condition

The condition from the problem statement can be expressed as follows: $\(C \times (A_l + A_{l+1} + \cdots + A_r) \leq T\)$

Since \(C \geq 1\), we can divide both sides by \(C\) to obtain: $\(A_l + A_{l+1} + \cdots + A_r \leq \left\lfloor \frac{T}{C} \right\rfloor\)$

Letting \(M = \left\lfloor \frac{T}{C} \right\rfloor\), the condition simplifies to “the sum of the interval is at most \(M\).” Note that if \(M = 0\), since \(A_i \geq 1\), no interval can ever satisfy the condition.

Naive Approach and Its Limitations

Consider exhaustively searching all valid intervals \((l, r)\). If we examine all pairs \((l, r)\) satisfying \(1 \leq l \leq r \leq N\) and \(r - l + 1 \geq K\), the number of intervals is \(O(N^2)\) in the worst case. Given the constraint \(N \leq 2 \times 10^6\), an \(O(N^2)\) algorithm will not meet the time limit.

Exploiting Monotonicity with the “Two Pointers” Technique

All elements \(A_i\) of the sequence are positive (\(A_i \geq 1\)). Therefore, expanding the interval to the right (increasing \(r\)) always increases the sum, and removing from the left (increasing \(l\)) always decreases the sum — this is the monotonicity property.

Using this property, we can apply the Two Pointers technique. When the left endpoint \(l\) is fixed, let \(r\) be the maximum right endpoint such that the condition (sum at most \(M\)) is satisfied. When we advance the left endpoint from \(l\) to \(l+1\), the interval sum decreases, so the new maximum right endpoint satisfying the condition is guaranteed to be at or to the right of the current \(r\). Therefore, we never need to move the right endpoint \(r\) back to the left — we only ever advance it to the right.

Algorithm

For each left endpoint \(l\), we find the maximum right endpoint \(r\) satisfying the condition using the two pointers technique.

1. Compute \(M = \lfloor T / C \rfloor\). If \(M = 0\) or \(N < K\), no valid interval exists, so output 0 and terminate.
2. Move the left endpoint \(l\) from \(0\) to \(N - K\) in order.
3. For each \(l\), as long as adding \(A_{r+1}\) to the current interval sum keeps it at most \(M\), advance the right endpoint \(r\) to the right and update the interval sum.
   • In the initial state (\(l=0\)), to ensure the minimum length \(K\), set \(r = K-1\) and initialize the interval sum to \(A_0 + \cdots + A_{K-1}\).
4. Once \(r\) has been extended as far as possible, if the interval sum is at most \(M\), the valid endpoints for intervals starting at \(l\) with length at least \(K\) range from \(l + K - 1\) to \(r\).
   • The number of such endpoints is \(r - (l + K - 1) + 1 = r - l - K + 2\), which we add to the answer.
5. In preparation for the next step (advancing the left endpoint to \(l+1\)), subtract \(A_l\) from the interval sum.
6. If \(r\) falls below the position required for the next minimum interval length (\(l + 1 + K - 1\)), advance \(r\) by one to the right and update the interval sum.

Complexity

• Time Complexity: \(O(N)\) Both the left pointer \(l\) and the right pointer \(r\) advance to the right at most \(N\) times each. Since each step is processed in \(O(1)\), the overall complexity is \(O(N)\), which comfortably fits within the time limit even for \(N \leq 2 \times 10^6\).
• Space Complexity: \(O(N)\) \(O(N)\) memory is used to store the input array \(A\).

Implementation Notes

• Incremental Update of Interval Sum: If we recompute the interval sum from scratch in \(O(N)\) at each loop iteration, the overall complexity degrades to \(O(N^2)\). Instead, by adding the incoming element and subtracting the outgoing element as the pointers move, we maintain the interval sum in \(O(1)\).

• Handling Corner Cases: When \(M = 0\) or \(N < K\), we return early before entering the main two-pointers loop, preventing out-of-bounds array accesses and unnecessary computation.

  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])

    A = list(map(int, input_data[4:]))

    M = T // C
    if M == 0 or N < K:
        print(0)
        return

    cur_sum = sum(A[:K])
    ans = 0
    r = K - 1

    for l in range(N - K + 1):
        while r + 1 < N and cur_sum + A[r + 1] <= M:
            r += 1
            cur_sum += A[r]

        if cur_sum <= M:
            ans += r - l - K + 2

        cur_sum -= A[l]
        if r < l + K:
            if r + 1 < N:
                r += 1
                cur_sum += A[r]
            else:
                break

    print(ans)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.