Overview

When selecting books from a contiguous interval on a bookshelf, the problem asks to choose an interval such that the total weight is at most \(K\) and the total satisfaction is maximized.

Analysis

In this problem, we need to select a “contiguous interval,” with the constraint that the total weight of the interval is at most \(K\). A naive brute-force approach (trying all combinations of \(l, r\)) would have a time complexity of \(O(N^2)\), which is impractical since \(N\) can be up to \(2 \times 10^5\).

However, both the weight and satisfaction of an interval can be computed efficiently using prefix sums. Additionally, the condition “the interval’s weight is at most \(K\)” can be checked efficiently by fixing the right endpoint \(r\) and appropriately moving the left endpoint \(l\).

The key technique here is the “two pointers method (two pointers).” By moving the right endpoint to the right while dynamically maintaining the smallest valid left endpoint, we eliminate unnecessary computations.

For example, if the interval \([l, r]\) exceeds the weight limit, we repeatedly move the left endpoint \(l\) to the right until the weight falls within the limit. In this way, we can examine each interval without using a double loop.

Algorithm

1. Precompute the prefix sums of satisfaction \(A\) and weight \(B\) respectively.
2. Use two pointers, left and right, to perform the two pointers method.
3. For each right, increment left until the weight of the interval \([left, right]\) is at most \(K\).
4. Compute the total satisfaction of the valid interval and update the maximum value.

By using prefix sums, we can compute the sum of an interval (satisfaction or weight) in \(O(1)\), which keeps the overall time complexity low.

Complexity

• Time complexity: \(O(N)\)
  Each element is accessed at most twice (once for the right pointer and once for the left pointer), so it runs in linear time.
• Space complexity: \(O(N)\)
  Required for the arrays storing the prefix sums.

Implementation Notes

• When computing prefix sums, prepending a 0 simplifies interval sum calculations (e.g., sum_A[right] - sum_A[left - 1]).

• Since left is monotonically non-decreasing with respect to right, we use a while loop inside the for loop to adjust it.

• sys.stdin.read is used for fast input reading.

  Source Code

import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+N]))
    B = list(map(int, data[2+N:2+2*N]))
    
    # 累積和を計算
    sum_A = [0] + list(accumulate(A))
    sum_B = [0] + list(accumulate(B))
    
    max_satisfaction = 0
    left = 1
    
    for right in range(1, N + 1):
        # 区間 [left, right] の重さを計算
        while sum_B[right] - sum_B[left - 1] > K:
            left += 1
        # 満足度の合計を更新
        satisfaction = sum_A[right] - sum_A[left - 1]
        if satisfaction > max_satisfaction:
            max_satisfaction = satisfaction
            
    print(max_satisfaction)

if __name__ == "__main__":
    main()

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