Overview

When traveling along a straight line from the base to the goal, we repeatedly “charge as much as possible” at each station, then determine whether the goal can be reached and, if so, the maximum remaining energy upon arrival.

Discussion

Key Insight

At first glance, this problem seems to involve a choice of “how much to charge at each station,” but charging as much as possible at each station is always optimal for maximizing remaining energy.

The reasoning is as follows:

• If the remaining energy upon arriving at a station is \(e\) and the charge amount is \(w\), then the remaining energy after charging is
  \(f(e)=\min(C, e+w)\)
  
• This \(f(e)\) has the property that the larger \(e\) is, the result never decreases (monotonically non-decreasing).
• Additionally, moving a distance \(d\) simply reduces the remaining energy to \(e-d\), so having a larger \(e\) is always advantageous.

In other words, “keeping the current remaining energy as large as possible” never works against future remaining energy (it only gets capped at the upper limit \(C\)).

Why a Naive Approach Is Difficult

If we try to explore or use DP to decide “how many units to charge at each station”: - The charge amounts \(W_i\) and capacity \(C\) can be as large as \(10^9\), making it infeasible to maintain that many states - \(N\) can also be up to \(2\times 10^5\)
so this is computationally impractical.

Instead, by leveraging the fact that the optimal behavior is unique (always charge to full), we can solve this with a simple simulation.

Unreachability Detection Is Also Handled Simultaneously

The “always charge to maximum” strategy maximizes the remaining energy at each point.
Therefore, if this strategy cannot reach the next point (remaining energy is less than the distance), then no other strategy can achieve a higher remaining energy, so it is impossible to reach.

Algorithm

1. Set initial remaining energy to \(e=C\) and previous position to prev=0.
2. Process the stations in order from the front (positions are given in ascending order).
   • Compute the distance from the previous point: \(d = P_i - prev\)
   • If \(e < d\), the vehicle stops midway, so output -1
   • Move: \(e \leftarrow e-d\)
   • Charge: \(e \leftarrow \min(C, e + W_i)\)
   • Update prev = P_i
3. Finally, check and move for the distance to the goal: \(d=L-prev\), in the same manner.
4. Output the remaining energy \(e\) upon reaching the goal.

(Example)
With capacity \(C=10\) and remaining energy \(e=3\), charging \(w=9\) gives
\(e \leftarrow \min(10, 3+9)=10\), and the overflow is discarded.

Complexity

• Time complexity: \(O(N)\) (each station is processed exactly once)
• Space complexity: \(O(1)\) (only a constant number of variables for current energy and position, etc.)

Implementation Notes

• Distances between stations and to the goal are computed as the difference from the previous position (updating prev).

• At each segment, always check e < d, and immediately output -1 if the destination cannot be reached.

• Charging must always be clipped by the capacity: e = min(C, e + w).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    L, N, C = map(int, input().split())
    e = C
    prev = 0

    for _ in range(N):
        p, w = map(int, input().split())
        d = p - prev
        if e < d:
            print(-1)
            return
        e -= d
        e = min(C, e + w)
        prev = p

    d = L - prev
    if e < d:
        print(-1)
        return
    e -= d
    print(e)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.