Overview

We want to find the maximum total satisfaction \(\sum A_i\) when selecting a “contiguous subarray” whose total weight does not exceed \(K\). Since the constraints are large, we need to search for the interval efficiently.

Analysis

When selecting a contiguous subarray \([l, r]\), the conditions are: - Total weight \(\sum_{i=l}^{r} B_i \le K\) - Maximize total satisfaction \(\sum_{i=l}^{r} A_i\)

Naively checking all intervals would give \(O(N^2)\) intervals (for \(N\) around \(2 \times 10^5\), this is up to about \(2 \times 10^{10}\)), which is far too slow (TLE).

The key observation is as follows:

• Since \(B_i \ge 1\), extending the right endpoint \(r\) to the right always increases the total weight (it never stays the same).
• For a fixed \(r\), the left endpoint \(l\) needed to satisfy \(\sum B_i \le K\) can be adjusted by “moving it to the right if necessary,” and there is never a need to move \(l\) back to the left.

In other words, by maintaining the left and right endpoints as pointers and repeating “advance the right endpoint by one → if it’s too heavy, advance the left endpoint to reduce weight,” we can update the maximum by scanning through everything just once.

(Example) - When extending the right endpoint causes the weight to exceed \(K\), remove the book at the left endpoint (advance the left endpoint) to reduce the weight back to \(\le K\).

Algorithm

We use the Two Pointers / Sliding Window technique.

• Initialize \(l=0\) (left endpoint), \(\text{sumA}=0\) (total satisfaction), \(\text{sumB}=0\) (total weight)
• Advance the right endpoint \(r=0,1,\dots,N-1\) in order:
  1. Add book \(r\) to the interval:
     \(\text{sumA} \mathrel{+}= A[r],\ \text{sumB} \mathrel{+}= B[r]\)
  2. If \(\text{sumB} > K\), shrink from the left until the condition is satisfied:
     while \(\text{sumB} > K\):
     • \(\text{sumA} \mathrel{-}= A[l],\ \text{sumB} \mathrel{-}= B[l]\)
     • \(l \mathrel{+}= 1\)
  3. At this point, the interval \([l, r]\) necessarily satisfies \(\sum B_i \le K\), so update the answer candidate: \(\text{ans} = \max(\text{ans}, \text{sumA})\)

The key point is that each element is “added once as the right endpoint” and “removed once as the left endpoint,” so the entire process runs in linear time.

Complexity

• Time complexity: \(O(N)\) (both \(l\) and \(r\) increase at most \(N\) times)
• Space complexity: \(O(N)\) (for storing arrays \(A, B\))

Implementation Notes

• Since \(K\) can be up to \(10^{15}\) and the totals can also be large, \(\text{sumA}\) and \(\text{sumB}\) must be handled as 64-bit integers (in Python this is automatic).

• Since the input can be large, using fast input methods like sys.stdin.buffer.read() is recommended to be safe.

• “There is always at least one interval satisfying the condition,” so the answer can always be updated (though in practice, initializing ans=0 causes no issues).

  Source Code

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    K = next(it)
    A = [next(it) for _ in range(N)]
    B = [next(it) for _ in range(N)]

    l = 0
    sumA = 0
    sumB = 0
    ans = 0

    for r in range(N):
        sumA += A[r]
        sumB += B[r]
        while sumB > K:
            sumA -= A[l]
            sumB -= B[l]
            l += 1
        if sumA > ans:
            ans = sumA

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.