Overview

A problem to find the maximum number of books that can be organized within a given time limit, using a contiguous interval of books.

Analysis

In this problem, we need to find a contiguous interval \([l, r]\) such that the total organization time of books in the interval is at most \(K\), and the interval length \(r - l + 1\) is maximized.

A naive approach would be to enumerate all intervals \([l, r]\) and compute the total time for each. However, this has a time complexity of \(O(N^2)\), which is impractical since \(N\) can be up to \(2 \times 10^5\) (it would result in TLE).

A key observation is the monotonicity property: “if an interval of length \(L\) can be organized within the time limit, then any shorter interval can also be organized.” In other words, we can use binary search to find the maximum feasible interval length.

Furthermore, to efficiently compute the sum of a fixed-length interval, we can use a sliding window (two-pointer technique) or prefix sums. In this implementation, we update the interval sum incrementally, allowing linear-time checking for each length.

Algorithm

1. Binary search on the interval length \(L\).
2. For each \(L\), determine whether there exists a contiguous subarray of length \(L\) whose sum is at most \(K\).
3. For the check, compute the sum of the first interval, then slide it one position at a time, adding and subtracting elements (sliding window).
4. Proceed with binary search while updating the maximum feasible length.

For example, given input N=5, K=10, A=[1, 2, 3, 4, 5]: - Check whether any interval of length 3, [1,2,3], [2,3,4], [3,4,5], has a sum of at most 10. - The sum of [2,3,4] is 9, which is OK → length 3 is feasible. - Try length 4 → the sum of [1,2,3,4] is 10, which is OK. - Ultimately, the maximum length is found to be 4.

Complexity

• Time complexity: \(O(N \log N)\)
  Each binary search step performs an \(O(N)\) check. The number of steps is \(O(\log N)\).
• Space complexity: \(O(N)\)
  Only the input array \(A\) needs to be stored.

Implementation Notes

• Set the binary search range to left = 0, right = N, and ensure that is_possible(0) returns True so that mid = 0 is handled correctly.
• The interval sum is updated incrementally as current_sum += A[i] - A[i - length] for efficiency.
• sys.stdin.read is used for fast input reading.

## Source Code

```python
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:]))

    # 二分探索で最大の長さを求める
    def is_possible(length):
        if length == 0:
            return True
        current_sum = sum(A[:length])
        if current_sum <= K:
            return True
        for i in range(length, N):
            current_sum += A[i] - A[i - length]
            if current_sum <= K:
                return True
        return False

    left, right = 0, N
    answer = 0
    while left <= right:
        mid = (left + right) // 2
        if is_possible(mid):
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
    print(answer)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.