Overview

Select a contiguous interval of bases \([l,r]\), and maximize the length of the cable that can be laid \(X_r - X_l\), subject to the constraint that the total cost is within the budget \(M\).

Analysis

• The chosen interval must be contiguous, with cost \(\sum_{i=l}^{r} C_i\) and length \(X_r - X_l\).
• Therefore, this becomes a subarray (contiguous interval) problem where we maximize \(X_r - X_l\) under the constraint that the total cost is at most \(M\).

Why a Naive Approach is Too Slow

• Trying all pairs \((l,r)\) results in \(O(N^2)\) intervals.
• Since \(N \le 2\times 10^5\), \(N^2\) can be up to \(4\times 10^{10}\), which cannot finish in a reasonable time (TLE).

Key Observation

• Since \(C_i \ge 1\), extending the right endpoint \(r\) to the right causes the total cost of the interval to monotonically increase (never decrease).
• If the cost exceeds \(M\), we can move the left endpoint \(l\) to the right to shrink the interval, which reduces the cost.
• This “move the right end rightward, and if it exceeds the budget, also move the left end rightward” approach means each pointer moves at most \(N\) times, so the entire process can be handled in \(O(N)\).

Algorithm

We use the Two Pointers / Sliding Window technique.

1. Initialize left endpoint \(l=0\), interval cost sum \(s=0\), and answer \(ans=0\).
2. Move the right endpoint \(r\) from \(0\) to \(N-1\) in order.
   • Expand the interval \([l,r]\) by setting \(s \leftarrow s + C_r\).
   • If \(s > M\), repeat the following until the condition is satisfied:
     • \(s \leftarrow s - C_l\)
     • \(l \leftarrow l + 1\)
   • Once the condition \(s \le M\) is satisfied, update \(ans\) with the current length \(X_r - X_l\).
3. Output \(ans\) as the final answer.

Simple Example

The idea is to shrink from the left when the total cost is exceeded: - Advancing \(r\) enlarges the interval → cost increases - If the budget is exceeded, advance \(l\) to shrink the interval → cost decreases - The value \(X_r - X_l\) at the point when the condition is satisfied becomes a candidate for the maximum possible length for that \(r\)

Complexity

• Time complexity: \(O(N)\)
  (Since \(l\) and \(r\) each increase at most \(N\) times)
• Space complexity: \(O(N)\)
  (For storing the \(X\) and \(C\) arrays)

Implementation Notes

• \(M\) can be up to \(10^{14}\), and \(\sum C_i\) can also be large, so the sum \(s\) must be handled with 64-bit integers (in Python, the standard int works fine).

• By shrinking with a while loop as long as s > M, we always maintain “the smallest \(l\) such that the total cost is at most \(M\)”.

• Even when \(l=r\), the length is \(X_r - X_l = 0\), which can be handled as-is without any issues.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    X = [0] * N
    C = [0] * N
    for i in range(N):
        x, c = map(int, input().split())
        X[i] = x
        C[i] = c

    l = 0
    s = 0
    ans = 0

    for r in range(N):
        s += C[r]
        while l <= r and s > M:
            s -= C[l]
            l += 1
        if l <= r:
            ans = max(ans, X[r] - X[l])

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.