Overview

A robot travels along a straight route from a base to a goal, charging at energy stations along the way, with the objective of maximizing the remaining battery upon reaching the goal. Since all stations are visited in order, this can be solved with a simulation.

Analysis

Key Insight: Charging Should Always Be Done

The most important observation in this problem is that there is no downside to charging at energy stations.

• Since stations are on the route, the robot necessarily passes through them (there is no detour cost).
• Charging only increases the battery (or caps it at battery capacity \(C\)); it never decreases it.
• Therefore, it is always optimal to charge at every station.

No Choice to Make → Simulation

At first glance, this appears to be a selection problem of “which stations to charge at,” but for the reasons above, charging at every station is optimal. This means the answer can be obtained by simply simulating the journey from the base to the goal in order.

Verification with a Concrete Example

For example, with \(L = 20, N = 2, C = 10\), and stations at \((5, 8)\) and \((15, 3)\):

1. Depart from base: Battery \(= 10\)
2. Arrive at position 5: Battery \(= 10 - 5 = 5\), after charging \(= \min(5 + 8, 10) = 10\)
3. Arrive at position 15: Battery \(= 10 - 10 = 0\), after charging \(= \min(0 + 3, 10) = 3\)
4. Arrive at goal (position 20): Battery \(= 3 - 5 = -2 < 0\) → Cannot reach, output -1

Algorithm

1. Initialize the battery to \(C\) (fully charged) and the current position to \(0\) (base).
2. Process each energy station in order:
   • Decrease the battery by the distance from the current position to the station.
   • If the battery becomes negative, output -1 and terminate (the robot stopped midway).
   • Add the charging amount, and take min to ensure it does not exceed the battery capacity \(C\).
3. Decrease the battery by the distance from the last station (or from the base if there are no stations) to the goal.
4. If the battery is negative, output -1; otherwise, output the remaining battery.

Complexity

• Time complexity: \(O(N)\) — each station is processed exactly once
• Space complexity: \(O(N)\) — for storing station information (can be reduced to \(O(1)\) with sequential reading)

Implementation Notes

• Watch out for overflow: \(L\) and \(C\) can be up to \(10^9\), but in Python there is no integer overflow, so this is not an issue. In languages like C++, you need to use long long.

• Case with 0 stations: If there are no stations, the remaining battery is \(C - L\) if \(C \geq L\), otherwise -1. This is handled correctly since the loop simply does not execute.

• Charging cap: Don’t forget to limit the battery so it does not exceed capacity using min(battery + w, C). Because of this limit, charging too early may result in “overflow” that is wasted, but this is never a reason not to charge (since charging never causes harm).

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    L = int(input_data[idx]); idx += 1
    N = int(input_data[idx]); idx += 1
    C = int(input_data[idx]); idx += 1
    
    stations = []
    for i in range(N):
        p = int(input_data[idx]); idx += 1
        w = int(input_data[idx]); idx += 1
        stations.append((p, w))
    
    # Start with full battery C, consume distance to move, charge at stations (capped at C)
    # This is a straightforward simulation since we must visit all stations in order
    # (there's no choice to skip - we always pass through them, and charging is always beneficial)
    
    # Wait - is charging always beneficial? Yes, because charging increases or maintains battery,
    # and we want to maximize remaining battery at the end. There's no downside to charging.
    
    battery = C
    prev_pos = 0
    
    for p, w in stations:
        dist = p - prev_pos
        battery -= dist
        if battery < 0:
            print(-1)
            return
        battery = min(battery + w, C)
        prev_pos = p
    
    # Travel from last station to goal
    dist = L - prev_pos
    battery -= dist
    if battery < 0:
        print(-1)
        return
    
    print(battery)

solve()

This editorial was generated by claude4.6opus-thinking.