Overview

The car’s travel time is always a constant \(G\) seconds, so the only thing that can be shortened is the “time spent stopping at toll gates to pay.” When ETC can be used to skip payments at exactly \(K\) consecutive toll gates, we choose the skipped interval to minimize the total time.

Analysis

• Since the speed is constant at \(1\) m per second, the travel time from the entrance to the destination (distance \(G\) m) is always \(G\) seconds.
  Regardless of where the toll gate positions \(D_i\) are, the arrival time doesn’t change if we exclude the stopping time (you are only delayed by the amount of time you stop).
• Therefore, the total time until arrival is
  $\( \text{Total time} = G + (\text{total seconds spent on payments}) \)$
• When using ETC, the payment time becomes \(0\) at exactly \(K\) consecutive toll gates. In other words,
  • If the original total payment time is \(S=\sum_{i=1}^{N} T_i\),
  • The total time is reduced by exactly the sum of payment times of the \(K\) toll gates included in the ETC interval.
• Therefore, to minimize the total time, we should choose the interval that maximizes “the sum of \(T\) over \(K\) consecutive elements.” $\( \text{Answer} = G + \left(S - \max_{\text{consecutive }K\text{ elements}} \sum T_i\right) \)$

A naive approach of “summing \(K\) elements for each of the \(N-K+1\) intervals” results in \(O(NK)\), which is too slow given the constraints of up to \(2\times 10^5\).

Instead, we use a method that efficiently updates the interval sum (sliding window) to find the maximum interval sum in \(O(N)\).

Algorithm

1. Read \(T_1,\dots,T_N\) from input and compute the total sum \(S=\sum T_i\) (\(D_i\) is not needed here).
2. Compute the sum of the first interval \([1, K]\) as window.
3. Slide the interval one position to the right at a time:
   • Add the new entering element and subtract the leaving element to update
     $\( \text{window} \leftarrow \text{window} + T_i - T_{i-K} \)$ (sliding window).
   • Maintain the maximum interval sum in best.
4. The answer is \(G + (S - \text{best})\).

(Example) When \(T=[3,1,4,1,5],\ K=2\), the sums of length-2 intervals are \(4,5,5,6\), so the maximum is \(6\) (the last pair \(1+5\)).
The total payment sum is \(14\), so the minimum time spent on payments is \(14-6=8\), and the total time is \(G+8\).

Complexity

• Time complexity: \(O(N)\) (finding the maximum interval sum in a single pass)
• Space complexity: \(O(N)\) (for storing \(T\); can be reduced to \(O(1)\) with an implementation that doesn’t store it)

Implementation Notes

• Since the travel time is always \(G\) seconds, \(D_i\) is read but not used (in the code it is discarded into _).

• \(T_i\) and the total sum can be up to \(10^9\), and \(N\) can be up to \(2\times 10^5\), so the total can be up to approximately \(2\times 10^{14}\). Python integers handle this safely, but in other languages, 64-bit integers are required.

• Since it must be exactly \(K\) toll gates, the maximum interval sum must only consider intervals of exactly length \(K\) (the length must not be varied).

  Source Code

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    K = next(it)
    G = next(it)

    T = [0] * N
    total = 0
    for i in range(N):
        _ = next(it)          # D_i (unused)
        ti = next(it)
        T[i] = ti
        total += ti

    window = sum(T[:K])
    best = window
    for i in range(K, N):
        window += T[i] - T[i - K]
        if window > best:
            best = window

    ans = G + (total - best)
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.