Overview

This is a problem where you select a contiguous subarray whose total price is at most \(K\), and maximize the total satisfaction \(A\) of that subarray. To efficiently search for subarrays satisfying the condition, we use the two-pointer technique (sliding window).

Analysis

Key Observation

• The total price \(B_l+\cdots+B_r\) of the subarray \([l, r]\) must be at most the constraint \(K\).
• Here, the fact that \(B_i \ge 1\) (positive values) is extremely important. Increasing the right endpoint \(r\) always increases the total price, and increasing the left endpoint \(l\) always decreases the total price.

This monotonicity enables the operation of “extending the right endpoint, and if the condition is violated, shrinking from the left endpoint to restore it.”

Why a Naive Approach Fails

If we try all subarrays \((l, r)\), there are \(O(N^2)\) subarrays. Since \(N \le 2\times 10^5\), \(O(N^2)\) is approximately \(4\times 10^{10}\), which will not fit within the time limit (TLE).

How to Solve It

• Move the right endpoint \(r\) from left to right, maintaining the subarray \([l, r]\)
• If the total price exceeds \(K\), advance the left endpoint \(l\) to reduce the total price
• At that point, update the maximum satisfaction total for subarrays satisfying the condition

With this method, each element is “added once as a right endpoint” and “removed once as a left endpoint,” so the overall complexity is \(O(N)\).

(Small example) - If the total of \(B\) becomes too large, removing from the left always decreases the total (because \(B_i>0\)) - Therefore, we can efficiently find the “maximum subarray satisfying the condition” for each right endpoint

Algorithm

We manage the subarray \([l, r]\) using the two-pointer technique, maintaining the following: - sumB: the total price of the current subarray - sumA: the total satisfaction of the current subarray

Procedure: 1. Initialize with \(l=0\), sumA=0, sumB=0, ans=0. 2. Advance the right endpoint from \(r=0\) to \(N-1\) in order: - Add to the subarray with sumA += A[r], sumB += B[r] - While sumB > K, shrink by moving the left endpoint: - sumA -= A[l], sumB -= B[l], l += 1 - Since the condition sumB <= K is now satisfied, update ans = max(ans, sumA) 3. Output ans (even if no subarray satisfies the condition, ans=0 remains, which is correct)

Key points: - The right endpoint \(r\) only moves in one direction from \(0 \to N-1\) - The left endpoint \(l\) also only moves in one direction Therefore, the total number of updates is linear.

Complexity

• Time complexity: \(O(N)\) (\(l\) and \(r\) each increase at most \(N\) times)
• Space complexity: \(O(N)\) (for storing the input arrays \(A, B\). With an implementation that doesn’t store them, \(O(1)\) is also possible)

Implementation Notes

• Since \(K\) can be up to \(10^{14}\), the total price sumB must be handled with 64-bit integers (in Python this is automatic).

• The shrinking process with while sumB > K advances the left endpoint until the subarray is guaranteed to satisfy the condition again.

• Even if no subarray satisfies the condition, initializing ans to \(0\) ensures correct output.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        a, b = map(int, input().split())
        A[i] = a
        B[i] = b

    l = 0
    sumA = 0
    sumB = 0
    ans = 0

    for r in range(N):
        sumA += A[r]
        sumB += B[r]
        while l <= r and sumB > K:
            sumA -= A[l]
            sumB -= B[l]
            l += 1
        if sumB <= K:
            if sumA > ans:
                ans = sumA

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.