Overview

This problem asks you to select a contiguous interval of shops that can be purchased with at most \(K\) money, maximizing the total satisfaction. It can be efficiently solved using the classic Two Pointers (Sliding Window) technique.

Analysis

Naive Approach

If we enumerate all intervals \((l, r)\), there are \(O(N^2)\) possible intervals, and computing the sum for each takes \(O(N^3)\) in the worst case (\(O(N^2)\) even with prefix sums). Since \(N \leq 2 \times 10^5\), even \(O(N^2)\) is too slow.

Key Observation

All prices \(B_i\) are positive values (\(B_i \geq 1\)). This is a very important property, which implies the following:

• Extending the interval to the right always increases the total price.
• Shifting the left endpoint to the right always decreases the total price.

Because of this monotonicity, the two pointers technique can be applied.

Let’s consider a concrete example. Suppose \(K = 10\) and the shops are as follows:

Shop	1	2	3	4
\(A_i\)	5	3	8	2
\(B_i\)	4	3	6	2

When the right endpoint is fixed at \(r = 3\) (shop 3), \(B_1 + B_2 + B_3 = 13 > 10\), so we shift the left endpoint to the right. Then \(B_2 + B_3 = 9 \leq 10\), which satisfies the condition. At this point, the satisfaction is \(3 + 8 = 11\).

Algorithm

Using the two pointers technique, we maintain two pointers: left endpoint \(l\) and right endpoint \(r\).

1. Initialize with left endpoint \(l = 0\), current satisfaction sum \(\text{sumA} = 0\), and price sum \(\text{sumB} = 0\).
2. Move the right endpoint \(r\) from \(0\) to \(N-1\) in order:
   • Add \(A[r]\) and \(B[r]\) to \(\text{sumA}\) and \(\text{sumB}\), respectively.
   • While \(\text{sumB} > K\), remove the leftmost shop from the interval (subtract \(A[l]\) and \(B[l]\), then increment \(l\) by 1).
   • If \(\text{sumB} \leq K\), the interval \([l, r]\) satisfies the condition, so update \(\text{ans} = \max(\text{ans}, \text{sumA})\).
3. Output the final \(\text{ans}\).

Key Point: If \(l\) exceeds \(r\) (i.e., \(l = r + 1\)), it means “even shop \(r\) alone has a price exceeding \(K\).” In this case, \(\text{sumB} = 0\) which does not satisfy \(\text{sumB} > K\), so the condition check \(\text{sumB} \leq K\) naturally handles it, and the answer remains \(0\) without being updated.

Why is this correct?: When the right endpoint \(r\) is fixed, finding the smallest left endpoint \(l\) such that the total price is at most \(K\) gives the interval that maximizes the total satisfaction (since all \(A_i\) are positive, a wider interval always yields greater satisfaction). With the two pointers technique, \(l\) increases monotonically throughout the entire process, so the optimal \(l\) is efficiently found for every \(r\).

Complexity

• Time complexity: \(O(N)\) — Both the left endpoint \(l\) and the right endpoint \(r\) advance at most \(N\) times each.
• Space complexity: \(O(N)\) — For storing arrays \(A\) and \(B\).

Implementation Notes

• Since \(K\) can be as large as \(10^{14}\), you need to use long long in languages like C++. In Python, integer overflow does not occur, so no special attention is needed.

• If no interval satisfies the condition, the answer is \(0\). Setting the initial value to \(0\) handles this naturally.

• Since the input can be large, reading all input at once with sys.stdin.buffer.read() can speed things up.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i] = int(input_data[idx]); idx += 1
        B[i] = int(input_data[idx]); idx += 1
    
    ans = 0
    current_sum_a = 0
    current_sum_b = 0
    left = 0
    
    for right in range(N):
        current_sum_a += A[right]
        current_sum_b += B[right]
        
        while current_sum_b > K and left <= right:
            current_sum_a -= A[left]
            current_sum_b -= B[left]
            left += 1
        
        if current_sum_b <= K and left <= right + 1:
            if left <= right:
                ans = max(ans, current_sum_a)
            elif left == right + 1:
                # All elements were removed, no valid interval ending at right
                pass
            else:
                ans = max(ans, current_sum_a)
    
    # Simpler logic: if left <= right after the while loop, we have a valid interval
    # Let me redo this cleanly
    
    ans = 0
    current_sum_a = 0
    current_sum_b = 0
    left = 0
    
    for right in range(N):
        current_sum_a += A[right]
        current_sum_b += B[right]
        
        while current_sum_b > K and left <= right:
            current_sum_a -= A[left]
            current_sum_b -= B[left]
            left += 1
        
        if current_sum_b <= K:
            ans = max(ans, current_sum_a)
    
    print(ans)

main()

---

This editorial was generated by claude4.6opus-thinking.