Overview

This problem asks you to minimize the total travel time when driving on a highway by using an ETC card to skip exactly \(K\) consecutive toll gates.

Analysis

Problem Breakdown

First, let’s organize the time it takes for Takahashi to reach his destination.

• Travel time: Moving \(G\) meters from the entrance to the destination at \(1\) meter per second takes \(G\) seconds
• Payment time: Each toll gate \(i\) takes \(T_i\) seconds

The total time without using the ETC card is: $\(\text{Base time} = G + \sum_{i=1}^{N} T_i\)$

Key Insight

Using the ETC card allows you to skip payment at exactly \(K\) consecutive toll gates.

In other words, to find the minimum time, we should skip the consecutive \(K\) toll gates that have the maximum total payment time.

\[\text{Minimum time} = \text{Base time} - \text{(Maximum sum of payment times for $K$ consecutive toll gates)}\]

Problem with the Naive Approach

If we naively calculate the sum of payment times for each consecutive \(K\) toll gates: - Number of starting positions: \(N - K + 1\) possibilities - For each candidate, adding \(K\) elements: \(O(K)\) - Total: \(O(N \times K)\)

When \(N\) and \(K\) are at most \(2 \times 10^5\), this results in up to \(4 \times 10^{10}\) calculations, causing TLE.

Solution: Prefix Sum

Using Prefix Sum, we can calculate the sum of any interval in \(O(1)\).

Define the prefix sum \(S\) as follows: $\(S[0] = 0, \quad S[i] = T_1 + T_2 + \cdots + T_i\)$

Then, the sum of interval \([i, i+K-1]\) (or \([i, i+K)\) in 0-indexed) is: $\(T_i + T_{i+1} + \cdots + T_{i+K-1} = S[i+K] - S[i]\)$

Algorithm

1. Read the input
2. Calculate the base time \(G + \sum T_i\)
3. Calculate the prefix sum of payment times \(T\)
4. For all starting positions \(i = 0, 1, \ldots, N-K\), calculate the sum of consecutive \(K\) elements \(S[i+K] - S[i]\) and find the maximum
5. Subtract the maximum from the base time and output the result

Concrete Example

For \(N=5, K=2, G=100\) with payment times \(T = [3, 7, 2, 8, 1]\):

• Prefix sum: \(S = [0, 3, 10, 12, 20, 21]\)
• Sum of 2 consecutive elements:
  • \(i=0\): \(S[2] - S[0] = 10 - 0 = 10\) (\(T_1 + T_2 = 3 + 7\))
  • \(i=1\): \(S[3] - S[1] = 12 - 3 = 9\) (\(T_2 + T_3 = 7 + 2\))
  • \(i=2\): \(S[4] - S[2] = 20 - 10 = 10\) (\(T_3 + T_4 = 2 + 8\))
  • \(i=3\): \(S[5] - S[3] = 21 - 12 = 9\) (\(T_4 + T_5 = 8 + 1\))
• Maximum: \(10\)
• Minimum time: \(100 + 21 - 10 = 111\) seconds

Complexity

• Time complexity: \(O(N)\)
  • Prefix sum calculation: \(O(N)\)
  • Maximum value search: \(O(N - K + 1) = O(N)\)
• Space complexity: \(O(N)\)
  • \(O(N)\) for the prefix sum array

Implementation Notes

• Making the prefix sum array have \(N+1\) elements with \(S[0] = 0\) simplifies interval calculations
• Since \(T_i\) and \(G\) can be up to \(10^9\) and the total sum can become large, 64-bit integers are needed. However, in Python, arbitrary-precision integers are used automatically, so there’s no need to worry.

Source Code

def solve():
    N, K, G = map(int, input().split())
    
    D = []
    T = []
    for _ in range(N):
        d, t = map(int, input().split())
        D.append(d)
        T.append(t)
    
    # Base time: travel time G seconds + payment time at all toll gates
    total_T = sum(T)
    base_time = G + total_T
    
    # ETC card allows skipping exactly K consecutive toll gates
    # By choosing interval [i, i+K-1] to skip, we save T[i] + T[i+1] + ... + T[i+K-1]
    # Find the maximum savings
    
    # Use prefix sum to efficiently calculate sum of K consecutive elements
    # prefix_sum[i] = T[0] + T[1] + ... + T[i-1]
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i + 1] = prefix_sum[i] + T[i]
    
    # Find the maximum payment time for K consecutive toll gates
    max_saving = 0
    for i in range(N - K + 1):
        # Sum of interval [i, i+K-1]
        saving = prefix_sum[i + K] - prefix_sum[i]
        max_saving = max(max_saving, saving)
    
    # Minimum time = base time - maximum savings
    answer = base_time - max_saving
    print(answer)

solve()

---

This editorial was generated by claude4.5opus.