Overview

A problem where you purchase products from shops in a contiguous interval and maximize the total satisfaction obtainable within a budget of \(K\).

Analysis

In this problem, you need to select an interval \([l, r]\) and buy products from all shops within that interval. The goal is to maximize the total satisfaction while keeping the total price of the interval at most \(K\).

A naive approach would be to enumerate all intervals \([l, r]\). However, this has a time complexity of \(O(N^2)\), which is impractical for the constraint \(N \leq 2 \times 10^5\) (it would result in TLE).

The key observation is that “the selected interval is contiguous.” This makes the two pointers technique (sliding window) effective. Specifically, we extend the right endpoint \(r\), and when the total price exceeds \(K\), we shrink the left endpoint \(l\), searching for the optimal interval in this manner.

Additionally, to efficiently compute the sum of each interval, it is convenient to precompute prefix sums.

Algorithm

1. Create a prefix sum array \(acc_A\) for satisfaction and a prefix sum array \(acc_B\) for prices. Using these, the sum of any interval \([l, r)\) can be computed in \(O(1)\).
2. Using the two pointers technique, find the maximum value of $\( acc_A[r] - acc_A[l] \)\( while satisfying the condition \)acc_B[r] - acc_B[l] \leq K$.
3. Move the right endpoint \(r\) from \(0\) to \(N\), advancing the left endpoint \(l\) appropriately to explore all valid intervals.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• By prepending \(0\) to the prefix sum arrays, the sum of interval \([l, r)\) can be uniformly handled as \(acc[r] - acc[l]\), which is convenient.

• In the two pointers technique, by fixing the right endpoint and moving the left endpoint, we find the largest interval that satisfies the condition.

• Intervals that do not satisfy the condition are immediately excluded by adjusting with a while loop.

  Source Code

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = [0] * N
    B = [0] * N
    
    idx = 2
    for i in range(N):
        A[i] = int(data[idx])
        B[i] = int(data[idx+1])
        idx += 2

    # 累積和を計算
    acc_A = [0] + list(accumulate(A))
    acc_B = [0] + list(accumulate(B))
    
    max_satisfaction = 0
    left = 0
    
    for right in range(N+1):
        while acc_B[right] - acc_B[left] > K:
            left += 1
        if acc_B[right] - acc_B[left] <= K:
            max_satisfaction = max(max_satisfaction, acc_A[right] - acc_A[left])
    
    print(max_satisfaction)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.