Overview

This problem asks us to minimize the total of travel time to the destination and waiting time at toll booths. Since travel time is constant, we find the shortest time by using the ETC card to maximize the “sum of waiting times at \(K\) consecutive toll booths” and subtracting that from the total waiting time.

Analysis

The time it takes Takahashi to reach the destination can be broken down into two components:

1. Travel time: Since he travels the distance \(G\) from the entrance to the destination at speed \(1\), this always takes \(G\) seconds.
2. Waiting time: The total of stopping times \(T_i\) at each toll booth. However, by using the ETC card, the waiting time at \(K\) consecutive toll booths can be reduced to \(0\).

To find the shortest time, we need to find the interval where the “sum of waiting times at \(K\) consecutive toll booths” is maximized, and subtract that amount from the total waiting time.

Naive Approach

If we consider summing the waiting times of \(K\) toll booths starting from every possible position (using a double loop), the time complexity is \(O(N \times K)\). Given the constraints where \(N, K \leq 2 \times 10^5\), this would require up to about \(4 \times 10^{10}\) operations, which will not fit within the time limit (typically about 2 seconds).

Efficient Approach

To efficiently compute “sums of consecutive intervals,” we use the sliding window technique. The sums of adjacent intervals (e.g., \([T_1, \dots, T_K]\) and \([T_2, \dots, T_{K+1}]\)) share most of their elements. Therefore, we can compute the next interval’s sum in \(O(1)\) by simply subtracting the “element leaving the window (\(T_1\))” from the previous sum and adding the “element entering the window (\(T_{K+1}\))”.

Algorithm

1. Compute the total sum of all toll booth waiting times, total_waiting_time.
2. Compute the sum of waiting times for the first \(K\) toll booths, and set it as the current maximum max_saved_time.
3. Slide the window one position to the right at a time, repeating the following operations \(N-K\) times:
   • current sum = previous sum - (waiting time leaving on the left) + (waiting time entering on the right)
   • Update max_saved_time.
4. Output the final answer as G + total_waiting_time - max_saved_time.

Complexity

• Time complexity: \(O(N)\)
  • Computing the total waiting time takes \(O(N)\), and the sliding window traversal takes \(O(N)\), so the overall time is linear.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the waiting times of each toll booth in a list.

Implementation Notes

• Fast input: Since \(N\) can be as large as \(2 \times 10^5\), it is efficient to read all input at once using methods like sys.stdin.read().split().

• Index management: When implementing the sliding window, be careful with loop bounds to avoid accessing out-of-range array indices.

• Handling distances \(D_i\): In this problem, travel time is determined solely by the distance \(G\), and the positions \(D_i\) of each toll booth do not directly affect the computation (since there is a condition that all toll booths are before the destination). Therefore, the problem can be solved by focusing only on the values of \(T_i\).

  Source Code

import sys

def main():
    # 入力を一括で読み込み、スペースや改行で分割してリストにする
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 料金所の数, K: ETCで通過する料金所の数, G: 目的地までの距離
    N = int(input_data[0])
    K = int(input_data[1])
    G = int(input_data[2])
    
    # 各料金所の待ち時間 T_i を抽出する
    # 入力形式は N K G の後に D_i T_i が N 個続くため、T_i はインデックス 4, 6, 8, ... にある
    T = [int(input_data[i]) for i in range(4, 4 + 2 * N, 2)]
    
    # 全ての料金所での待ち時間の合計
    total_waiting_time = sum(T)
    
    # 連続する K 個の料金所の待ち時間の合計の最大値をスライディングウィンドウで求める
    # 最初の K 個の合計を初期値とする
    current_window_sum = sum(T[:K])
    max_saved_time = current_window_sum
    
    # ウィンドウを一つずつずらして最大合計（節約できる時間）を更新する
    for i in range(N - K):
        # 抜ける要素を引いて、新しく入る要素を足す
        current_window_sum = current_window_sum - T[i] + T[i + K]
        if current_window_sum > max_saved_time:
            max_saved_time = current_window_sum
            
    # 最短時間 = (移動距離 G / 速度 1) + (全待ち時間の合計) - (ETCで節約できた待ち時間)
    print(G + total_waiting_time - max_saved_time)

if __name__ == '__main__':
    main()

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