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 solved efficiently using the two-pointer technique (sliding window).

Analysis

Problem Reformulation

This problem can be reduced to “selecting a contiguous subarray and maximizing \(X_r - X_l\) under the constraint that the total cost is at most \(M\).”

Naive Approach and Its Issues

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

Using prefix sums, we can compute costs in \(O(1)\), but this still gives \(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, the minimum left endpoint \(l\) such that the cost is at most \(M\) is uniquely determined, and as \(r\) increases, \(l\) also increases monotonically (or stays the same). This satisfies the conditions for applying the two-pointer technique.

Algorithm

We solve this using the two-pointer technique.

1. Initialize left endpoint left = 0 and current cost current_cost = 0
2. Move the right endpoint right from \(0\) to \(N-1\) in order
3. For each right:
   • Add C[right] to current_cost
   • While current_cost > M, subtract C[left] and move 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 adding	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\) when selecting interval \([0, 1]\).

Complexity

• Time Complexity: \(O(N)\)
  • right advances \(N\) times from \(0\) to \(N-1\)
  • left advances at most \(N\) times in total throughout the execution
  • 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 total cost can become very large. In Python, there’s no worry 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 gives \(0\).
• Checking valid intervals: Calculate the length only when left <= right and current_cost <= M. If no bases fit within the budget, the maximum length \(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 two-pointer technique
    # Select a contiguous interval [l, r] and maximize X[r] - X[l] with total cost at most M
    
    max_length = 0
    current_cost = 0
    left = 0
    
    for right in range(N):
        # Add the right-th base
        current_cost += C[right]
        
        # While cost exceeds M, shrink from the left
        while current_cost > M and left <= right:
            current_cost -= C[left]
            left += 1
        
        # If current interval is valid (cost is at most M), calculate 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.