Overview

Among multiple toll booths on a highway, this problem asks to minimize the total travel time by passing through exactly \(K\) consecutive toll booths non-stop using ETC.

Analysis

Since Takahashi travels from the entrance to the destination at a speed of 1 meter per second, the simple travel time is \(G\) seconds. During this time, if he stops and pays at every toll booth, the total stopping time is added. In other words, we can naively think of it as follows:

• Time when stopping at all toll booths = \(G + \sum_{i=0}^{N-1} T_i\)

However, with the ETC card, he can pass through \(K\) consecutive toll booths without stopping. This means the stopping time for that section can be eliminated.

Therefore, the goal is to find “the section of \(K\) consecutive toll booths where the total payment time is maximized” and subtract that total from the overall stopping time to obtain the minimum time.

If we naively compute the sum for every section, it would be \(O(NK)\), which is too slow when the constraints are large (\(N\) up to \(2 \times 10^5\)). Instead, we use prefix sums and a sliding window approach to efficiently compute the interval sums.

Algorithm

1. First, precompute the prefix sums of the stopping times. This allows us to compute the total payment time for any interval \([l, r]\) in \(O(1)\).

   • prefix_sum[i] = \(T[0] + T[1] + \cdots + T[i-1]\)
   • Sum of interval \([l, r]\) = prefix_sum[r+1] - prefix_sum[l]

2. Consider choosing \(K\) consecutive toll booths as the section where the ETC card is used. There are \(N - K + 1\) such sections in total.

3. Compute the total payment time for each section using prefix sums, and select the one with the largest payment time. Call this max_etc_saving.

4. The final minimum time is: $\( \text{minimum time} = G + \left(\sum_{i=0}^{N-1} T_i\right) - \text{max\_etc\_saving} \)$

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• When building the prefix sum, setting prefix_sum[0] = 0 at the beginning simplifies the interval sum calculation.

• When computing interval sums with the sliding window, the sum corresponding to interval [i, i+K-1] is prefix_sum[i+K] - prefix_sum[i].

• To read input efficiently, sys.stdin.read is used.

  Source Code

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    G = int(data[idx]); idx += 1
    
    D = [0]*N
    T = [0]*N
    for i in range(N):
        D[i] = int(data[idx]); idx += 1
        T[i] = int(data[idx]); idx += 1

    # 累積和を計算: prefix_sum[i] = T[0] + ... + T[i-1]
    prefix_sum = [0] + list(accumulate(T))
    
    # ETCを使わない場合の合計時間 = 全Tの和
    total_stop_time = prefix_sum[N]
    
    min_etc_saving = 0
    
    # スライドウィンドウで連続K個のTの和を求める
    for i in range(N - K + 1):
        # ETCを使う区間: [i, i+K-1]
        etc_cost = prefix_sum[i + K] - prefix_sum[i]
        saving = etc_cost
        if saving > min_etc_saving:
            min_etc_saving = saving
            
    # 最短時間 = 走る時間 + 停止時間 - ETC節約分
    driving_time = G
    min_time = driving_time + total_stop_time - min_etc_saving
    print(min_time)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.