Overview

This problem asks us to find a contiguous subarray whose total weight is at most \(K\) and whose total satisfaction is maximized. It can be solved efficiently using the two pointers (sliding window) technique.

Analysis

Naive Approach and Its Issues

If we try all intervals \([l, r]\), there are \(O(N^2)\) combinations of \(l\) and \(r\). Even if we compute the weight and satisfaction of each interval in \(O(1)\) using prefix sums, since \(N\) can be up to \(2 \times 10^5\), \(O(N^2)\) would require approximately \(4 \times 10^{10}\) operations, which exceeds the time limit (TLE).

Key Observation

This problem has the following properties:

• The weights \(B_i\) are all positive values (at least \(1\))
• Therefore, expanding the interval to the right causes the total weight to monotonically increase
• Conversely, shifting the left endpoint to the right causes the total weight to monotonically decrease

Because of this monotonicity, when the right endpoint \(r\) is fixed, the range of left endpoints \(l\) for which the weight is at most \(K\) forms a contiguous range from some value onward. Furthermore, when \(r\) increases by \(1\), the lower bound of valid left endpoints either stays the same or moves to the right. In other words, the left endpoint never moves backward.

This property allows us to apply the two pointers technique.

Concrete Example

For example, with \(N=5\), \(K=10\), \(A = [3, 5, 2, 8, 1]\), \(B = [4, 3, 5, 6, 2]\):

• \(r=0\): Interval \([0,0]\), weight \(4 \leq 10\) → satisfaction \(3\)
• \(r=1\): Interval \([0,1]\), weight \(7 \leq 10\) → satisfaction \(8\)
• \(r=2\): Interval \([0,2]\), weight \(12 > 10\) → advance left to \([1,2]\), weight \(8 \leq 10\) → satisfaction \(7\)
• \(r=3\): Interval \([1,3]\), weight \(14 > 10\) → advance left to \([2,3]\), weight \(11 > 10\) → advance further to \([3,3]\), weight \(6 \leq 10\) → satisfaction \(8\)

As shown, the left endpoint never moves backward, and the entire process runs in \(O(N)\).

Algorithm

1. Initialize the left endpoint left to \(0\), and initialize the total weight sum_b and total satisfaction sum_a to \(0\)
2. Move the right endpoint right from \(0\) to \(N-1\) in order:
   • Add \(A[\text{right}]\) to sum_a and \(B[\text{right}]\) to sum_b
   • While sum_b > K, remove the leftmost book from the interval (subtract \(A[\text{left}]\) and \(B[\text{left}]\) from sum_a and sum_b, and increment left by \(1\))
   • If the current sum_a is greater than the current maximum answer, update the answer
3. Output the final maximum value

Complexity

• Time complexity: \(O(N)\) — right advances \(N\) times, and left advances at most \(N\) times in total, so the combined total is \(O(N)\)
• Space complexity: \(O(N)\) — needed to store arrays \(A\) and \(B\)

Implementation Notes

• Since \(K\) can be up to \(10^{15}\), each \(B_i\) up to \(10^9\), and \(N\) up to \(2 \times 10^5\), the total weight can reach approximately \(2 \times 10^{14}\). In Python there is no need to worry about integer overflow, but in C++ and similar languages, long long must be used

• When advancing the left endpoint in the while sum_b > K loop, left will never exceed right (because there always exists at least one interval consisting of a single book whose weight is at most \(K\))

• sys.stdin.buffer.read() is used for fast input

  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 = [int(input_data[idx + i]) for i in range(N)]; idx += N
    B = [int(input_data[idx + i]) for i in range(N)]; idx += N
    
    ans = 0
    sum_a = 0
    sum_b = 0
    left = 0
    
    for right in range(N):
        sum_a += A[right]
        sum_b += B[right]
        
        while sum_b > K:
            sum_a -= A[left]
            sum_b -= B[left]
            left += 1
        
        if sum_a > ans:
            ans = sum_a
    
    print(ans)

main()

---

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