Overview

Select a contiguous interval such that the total organizing time is at most \(K\), and find the maximum number of books (interval length) contained in that interval.

Analysis

This problem asks us to find the longest interval under the condition that “the sum of a contiguous subsequence is at most \(K\).”

If we naively try all intervals \([l,r]\), there are \(O(N^2)\) intervals, and computing the sum of each results in \(O(N^3)\) in the worst case. Even using prefix sums to compute each sum in \(O(1)\), it is still \(O(N^2)\).
With the constraint \(N \le 2 \times 10^5\), even \(O(N^2)\) is too slow.

The key observation here is:

• Since \(A_i \ge 1\), expanding the interval to the right (increasing \(r\)) causes the interval sum to monotonically increase.
• Conversely, shrinking the interval from the left (increasing \(l\)) causes the interval sum to monotonically decrease.

Due to this monotonicity, we can process everything in \(O(N)\) by repeating the operation: “advance the right endpoint by one, then advance the left endpoint until the condition is satisfied.”

Example: \(A=[3,1,4,1,5],\ K=6\)
We extend the right endpoint, and whenever the sum exceeds \(6\), we move the left endpoint to adjust. This way, the current interval is always “the longest possible interval that satisfies the condition,” and we can update the maximum length.

Algorithm

We use the Two Pointers / Sliding Window technique.

• Maintain a left endpoint \(l\), right endpoint \(r\), and current interval sum \(s\)
• Move \(r\) from left to right one step at a time, updating \(s += A[r]\)
• If \(s > K\), repeat the following until \(s \le K\):
  • \(s -= A[l]\)
  • \(l += 1\) (shrink the interval from the left)
• When the condition is satisfied, update the answer with the interval length \(r-l+1\)

Since both \(l\) and \(r\) increase at most \(N\) times, the entire process runs in linear time.

Complexity

• Time complexity: \(O(N)\) (each element enters and leaves the interval at most once)
• Space complexity: \(O(1)\) (only a constant number of variables besides the input array)

Implementation Notes

• \(K\) can be up to \(10^{15}\), and the sum can also be large, so Python’s int (arbitrary-precision integer) handles this safely (in C++, long long is required).

• When shrinking the left endpoint in the while s > K loop, make sure to always advance \(l\) and decrease the interval sum.

• If no book can be organized at all, no update occurs and ans=0 remains, so 0 is output as is.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, K = data[0], data[1]
    A = data[2:2+N]

    l = 0
    s = 0
    ans = 0
    for r, x in enumerate(A):
        s += x
        while s > K and l <= r:
            s -= A[l]
            l += 1
        if s <= K:
            ans = max(ans, r - l + 1)

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.