Overview

Given a bookshelf with \(N\) books lined up, the problem asks you to select a contiguous subarray such that the total weight is at most \(K\), and maximize the total satisfaction of the books in that subarray.

Analysis

1. Naive Approach (Brute Force)

First, consider examining all possible subarrays \([l, r]\). There are \(O(N^2)\) ways to choose a subarray, and computing the total weight and satisfaction for each one results in \(O(N^3)\) overall, or \(O(N^2)\) even with prefix sums. Given the constraint \(N \leq 2 \times 10^5\), an \(O(N^2)\) algorithm will not finish within the time limit.

2. Key Property: Monotonicity

The crucial point in this problem is that “all book weights \(B_i\) are positive”. When the total weight of a subarray \([l, r]\) exceeds \(K\), any subarray extended further to the right \([l, r+1], [l, r+2], \ldots\) will also have a total weight exceeding \(K\). Conversely, when the right endpoint \(r\) is fixed, moving the left endpoint \(l\) further to the right will cause the total weight (and similarly the total satisfaction) of the subarray to decrease or stay the same.

By leveraging this property — that the total value changes monotonically as we move the endpoints of the subarray — we can solve this efficiently using the “Two Pointers” technique (also known as the sliding window method).

Algorithm

Optimization Using Two Pointers

We move the left endpoint left and right endpoint right of the subarray while maintaining the condition that “the current total weight is at most \(K\)”.

1. Advance right one step at a time from \(0\) to \(N-1\).
2. Add the weight of the newly included book right to current_weight, and its satisfaction to current_satisfaction.
3. If current_weight exceeds \(K\), advance left to the right until the condition is satisfied, removing books from the subarray.
4. Once current_weight <= K holds, update the maximum value with the current subarray’s total satisfaction current_satisfaction.

In this method, both right and left move at most \(N\) times each. Therefore, the answer can be computed very efficiently.

Complexity

• Time Complexity: \(O(N)\)
  • The right pointer moves \(N\) times, and the left pointer moves at most \(N\) times in total, so the overall complexity is \(O(N)\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used for the arrays storing the input values \(A_i\) and \(B_i\).

Implementation Notes

• Fast I/O: Since \(N = 2 \times 10^5\) and the input size is large, in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() or similar methods.

• Variable Initialization: Initialize the maximum satisfaction max_satisfaction to \(0\). Due to the constraints, there is always at least one subarray with total weight at most \(K\), so the final answer will be a positive integer.

• Data Type for Total Weight: The cumulative sum of \(K\) and \(B_i\) can become very large (up to approximately \(2 \times 10^{14}\)), but since Python natively handles arbitrary-precision integers, there is no concern about overflow.

  Source Code

import sys

def solve():
    # 入力を標準入力から取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    
    # 満足度 A と 重さ B のリストを取得
    A = list(map(int, input_data[2:N+2]))
    B = list(map(int, input_data[N+2:2*N+2]))
    
    max_satisfaction = 0
    current_satisfaction = 0
    current_weight = 0
    left = 0
    
    # しゃくとり法 (Two Pointers) を用いて最大値を計算
    for right in range(N):
        current_weight += B[right]
        current_satisfaction += A[right]
        
        # 重さの合計が K を超える間、左端を縮める
        while current_weight > K and left <= right:
            current_weight -= B[left]
            current_satisfaction -= A[left]
            left += 1
        
        # 条件を満たす区間の場合、最大値を更新
        if current_weight <= K:
            if current_satisfaction > max_satisfaction:
                max_satisfaction = current_satisfaction
                
    print(max_satisfaction)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.