Overview

This problem asks us to maximize the length of fiber optic cable that can be laid by operating consecutive bases within a budget of \(M\) million yen. It can be efficiently solved using the two-pointer technique (sliding window).

Analysis

Problem Reformulation

This problem can be reduced to “selecting a contiguous subarray such that the sum of costs is at most \(M\), and maximizing \(X_r - X_l\).”

Naive Approach and Its Issues

If we enumerate all intervals \([l, r]\), there are \(O(N^2)\) ways to choose intervals, and if computing the cost for each interval takes \(O(N)\), the total complexity becomes \(O(N^3)\). With \(N \leq 2 \times 10^5\), this would result in TLE (Time Limit Exceeded).

Using prefix sums, we can compute the cost in \(O(1)\), but even then the complexity is \(O(N^2)\), which is still too slow.

Why the Two-Pointer Technique Works

This problem has the following properties: - Monotonicity: Expanding the interval increases the cost, and shrinking the interval decreases the cost - Contiguous interval: The selected bases must be consecutive

Due to these properties, when the right endpoint \(r\) is fixed, there is a unique minimum left endpoint \(l\) such that the cost is at most \(M\), and as \(r\) increases, \(l\) also monotonically increases (or stays the same). This satisfies the conditions for applying the two-pointer technique.

Algorithm

We solve this using the two-pointer technique (Two Pointers).

1. Initialize with left endpoint left = 0 and current cost current_cost = 0
2. Move the right endpoint right from \(0\) to \(N-1\) sequentially
3. For each right:
   • Add C[right] to current_cost
   • While current_cost > M, subtract C[left] and advance left to the right
   • If the interval is valid, calculate the length X[right] - X[left] and update the maximum
4. Output the maximum value

Concrete Example

Consider \(N = 4, M = 10\) with the following bases: - Base 1: position \(0\), cost \(3\) - Base 2: position \(5\), cost \(4\) - Base 3: position \(8\), cost \(5\) - Base 4: position \(15\), cost \(6\)

right	Cost after addition	left movement	Valid interval	Length
0	3	none	[0,0]	0
1	7	none	[0,1]	5
2	12 → 9	left: 0→1	[1,2]	3
3	15 → 11 → 6	left: 1→2→3	[3,3]	0

In this example, the maximum length is \(5\), achieved by selecting interval \([0, 1]\).

Complexity

• Time Complexity: \(O(N)\)
  • right advances \(N\) times from \(0\) to \(N-1\)
  • left advances at most \(N\) times throughout the entire process
  • Therefore, the total is \(O(N)\)
• Space Complexity: \(O(N)\)
  • Storing position array \(X\) and cost array \(C\)

Implementation Notes

• Overflow prevention: Since \(M\) and \(C_i\) can be as large as \(10^{14}\) or \(10^9\), the sum of costs can become very large. In Python, there is no concern about integer overflow, but in other languages, you need to use 64-bit integer types.
• Case when \(l = r\): When only one base is operating, the length is \(0\). In the code, simply calculating X[right] - X[left] naturally yields \(0\).
• Checking valid intervals: We only calculate the length when left <= right and current_cost <= M. If there is no base that fits within the budget, the maximum length of \(0\) is output.

Source Code

def solve():
    N, M = map(int, input().split())
    X = []
    C = []
    for _ in range(N):
        x, c = map(int, input().split())
        X.append(x)
        C.append(c)
    
    # Solve using the two-pointer technique
    # Select a contiguous interval [l, r] such that the sum of costs is at most M, and maximize X[r] - X[l]
    
    max_length = 0
    current_cost = 0
    left = 0
    
    for right in range(N):
        # Add the right-th base
        current_cost += C[right]
        
        # While the cost exceeds M, shrink from the left
        while current_cost > M and left <= right:
            current_cost -= C[left]
            left += 1
        
        # If the current interval is valid (cost is at most M), calculate the length
        if left <= right and current_cost <= M:
            length = X[right] - X[left]
            max_length = max(max_length, length)
    
    print(max_length)

solve()

---

This editorial was generated by claude4.5opus.