Overview

Given bases arranged in a straight line, the problem asks to select a contiguous interval \([l, r]\) of bases such that the total cost is within the budget of \(M\) (in units of 10,000 yen), and to find the maximum value of the interval length \(X_r - X_l\).

Analysis

The key insight for solving this problem is to focus on the monotonicity property: “the more you extend the selected interval to the right, the more the total required cost increases.”

If the cost of a certain interval \([l, r]\) does not exceed the budget \(M\), then you can either keep the left endpoint \(l\) fixed and increase \(r\) further, or move \(l\) to the right to shorten the interval, thereby exploring other valid intervals.

Why a naive approach doesn’t work

A naive approach that tries all combinations of intervals \((l, r)\) (using a double loop) would need to examine \(O(N^2)\) intervals. Since \(N = 2 \times 10^5\), the number of combinations can be up to \(4 \times 10^{10}\), which exceeds the time limit.

Therefore, we need a method that moves the left endpoint \(l\) one by one while efficiently managing the corresponding right endpoint \(r\).

Algorithm

Two-pointer approach

Let \(l\) be the left endpoint and \(r\) be the right endpoint of the interval. We search for the optimal interval using the following procedure:

1. Extend the right endpoint: As long as adding \(C_r\) to the current interval’s total cost does not exceed the budget \(M\), advance \(r\) one position at a time.
2. Update the maximum: When \(r\) can no longer be advanced, compute the length \(X_{r-1} - X_l\) of the interval \([l, r-1]\), and compare it with the current maximum to update it.
3. Shrink the left endpoint: Advance \(l\) one position to the right. At this point, subtract \(C_l\) from the total cost.
4. Repeat steps 1–3 until \(l\) reaches \(N\).

With this method, both \(l\) and \(r\) move at most \(N\) times each, significantly reducing the computational cost.

Complexity

• Time complexity: \(O(N)\)
  • Reading input takes \(O(N)\), and the two-pointer scan takes \(O(N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for arrays storing each base’s position \(X_i\) and cost \(C_i\).

Implementation Notes

• Fast I/O: Python’s input() function is slow, so when reading large amounts of data, using sys.stdin.read().split() to read everything at once and convert it to a list can reduce execution time.

• Bases exceeding the budget: If a single base’s cost \(C_i\) already exceeds the budget \(M\), care must be taken inside the two-pointer method to ensure that \(r\) does not fall behind \(l\).

• Index management: In the two-pointer method, managing the interval as a half-open interval \([l, r)\) simplifies the logic for adding and removing elements. In this code, \(r\) is implemented to point to the “next candidate to include.”

  Source Code

import sys

def solve():
    # 高速な入力読み込みのために、全ての入力を一度に読み込んで分割します。
    # この方法は、Pythonにおいて多くの入力（今回は約4*10^5個の整数）を処理する際に効率的です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 中継基地の数, M: 予算
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各基地の位置 X と稼働費用 C を格納するためのリストを事前に確保します。
    X = [0] * N
    C = [0] * N
    
    # 入力データから各基地の情報をパースします。
    # 基地の情報は位置の昇順で与えられることが保証されています。
    for i in range(N):
        X[i] = int(input_data[2 + 2*i])
        C[i] = int(input_data[3 + 2*i])
        
    max_len = 0
    r = 0
    current_cost = 0
    
    # 尺取り法（Two-pointer approach）を用いて、予算 M 以内で稼働させることができる
    # 連続する基地の区間 [l, r-1] を探索し、その最大長 X[r-1] - X[l] を求めます。
    # ここで l は区間の開始インデックス、 r-1 は終了インデックスです。
    for l in range(N):
        # 現在の合計費用 current_cost に次の基地 r の費用を加えても予算 M を超えない限り、
        # 右側のポインタ r を進めて区間を広げます。
        while r < N and current_cost + C[r] <= M:
            current_cost += C[r]
            r += 1
        
        # r > l の場合、少なくとも1つの基地が予算内で稼働可能です。
        # その区間 [l, r-1] における回線の長さ X[r-1] - X[l] を計算し、最大値を更新します。
        # 基地が1つのみの場合 (r = l + 1)、長さは X[l] - X[l] = 0 となります。
        if r > l:
            length = X[r-1] - X[l]
            if length > max_len:
                max_len = length
            
            # 次の開始位置 l+1 に備えて、現在の基地 l の費用を合計から差し引きます。
            current_cost -= C[l]
        else:
            # もし基地 l 自体の費用が予算 M を超えている場合、区間は空になります。
            # r を l+1 に進め、次のループで l が l+1 になったときに r = l となるようにします。
            r = l + 1
            current_cost = 0
            
    # 求まった最大長を出力します。
    sys.stdout.write(str(max_len) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.