Overview

This problem asks us to find a contiguous interval of books whose total weight is at most \(K\) and whose total satisfaction is maximized.

Analysis

A naive approach would be to compute the total weight and total satisfaction for every contiguous interval \((l, r)\), then find the maximum satisfaction among those that satisfy the condition. However, the time complexity of this approach is \(O(N^2)\), which would result in an extremely long execution time for this problem where \(N\) can be up to \(2 \times 10^5\).

An efficient solution is to use the “two-pointer technique” (sliding window). The two-pointer technique explores intervals by appropriately moving the left endpoint \(l\) and right endpoint \(r\), and since each element is processed at most twice, it can solve the problem in linear time.

Algorithm

1. Initialize the left endpoint \(l\) to 0, and move the right endpoint \(r\) sequentially from 0 to \(N-1\)
2. For each \(r\), add the weight and satisfaction of the current interval \([l, r]\) to \(current\_weight\) and \(current\_satisfaction\) respectively
3. If \(current\_weight > K\), move the left endpoint \(l\) to the right, subtracting \(B[l]\) and \(A[l]\) until the total weight becomes at most \(K\)
4. At each step, check the total satisfaction of the interval that satisfies the condition and update the maximum value

In this approach, both \(l\) and \(r\) move at most \(N\) times each, enabling efficient exploration.

Complexity

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

Implementation Notes

• When implementing the two-pointer technique, be careful that the left endpoint \(l\) does not exceed the right endpoint \(r\)

• It is important to correctly handle the case where the total weight exceeds \(K\) using a while loop

• Since input values can be large, sys.stdin.read is used for fast input processing

  Source Code

def main():
    import sys
    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]))
    
    left = 0
    current_weight = 0
    current_satisfaction = 0
    max_satisfaction = 0
    
    for right in range(n):
        current_weight += B[right]
        current_satisfaction += A[right]
        
        while current_weight > K:
            current_weight -= B[left]
            current_satisfaction -= A[left]
            left += 1
            
        if current_satisfaction > max_satisfaction:
            max_satisfaction = current_satisfaction
            
    print(max_satisfaction)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.