Overview

This problem asks whether an electric vehicle can travel through \(N\) sections by appropriately choosing whether to exchange batteries at charging stations along the way.

Analysis

Key Insights

1. The choice at charging stations can be determined greedily

   • Exchanging batteries sets the remaining charge to \(S_j\)
   • If \(S_j\) is greater than the current charge, exchanging is beneficial; otherwise, it’s better not to exchange
   • This is because having more battery charge increases the possibility of proceeding further

2. Simulation is sufficient

   • Simply traverse the sections in order and consider exchanging when there’s a charging station
   • Before traveling each section, check if the battery charge is at least \(1\)

Understanding Through a Concrete Example

For example, with \(N=3\), \(K=5\), \(D=[3, 4, 2]\), and a station with \(S=6\) between section 1 and section 2 (\(P=1\)):

1. Travel section 1: Battery \(5 \to 5-3=2\)
2. Arrive at station: Current \(2\) < \(S=6\), so exchange → Battery \(6\)
3. Travel section 2: Battery \(6 \to 6-4=2\)
4. Travel section 3: Battery \(2 \to 2-2=0\)
5. Successfully completed all sections!

Why the Greedy Approach is Correct

• Once you pass a station, you cannot return to it
• If you don’t exchange at a station with \(S_j\) greater than your current charge, you lose that “benefit”
• Conversely, exchanging for a smaller \(S_j\) only reduces your charge, which is a loss

Algorithm

1. Set initial battery charge to \(K\)
2. Process sections \(1\) through \(N\) in order:
   • Before traveling section \(i\), check if there’s a charging station just before it (\(P_j = i-1\))
   • If \(S_j\) is greater than the current battery charge, exchange
   • If battery charge is less than \(1\) before traveling, output No and terminate
   • Travel the section and reduce battery charge by \(D_i\)
3. After completing all sections, output Yes

[Start] --Section 1--> [Station?] --Section 2--> [Station?] --Section 3--> [Goal]
    K                  if at P=1         if at P=2

Complexity

• Time Complexity: \(O(N + M)\)

  • Processing each section once: \(O(N)\)
  • Checking each charging station once: \(O(M)\)

• Space Complexity: \(O(N + M)\)

  • Storing array \(D\): \(O(N)\)
  • Storing charging station information: \(O(M)\)

Implementation Notes

1. Pay attention to index correspondence

   • In the problem statement, sections are 1-indexed, but arrays are 0-indexed
   • A station “between section \(i\) and section \(i+1\)” is processed after completing section \(i\) in 0-indexed terms

2. Timing of travel judgment

   • Travel is possible if “battery charge is at least \(1\) just before traveling”
   • Even if the battery becomes \(0\) or less after traveling, it’s fine as long as it’s at least \(1\) before the next section
   • After completing the last section, it’s OK even if the battery is \(0\) or less

3. When there are no stations

   • To handle the case where \(M = 0\) correctly, don’t forget to check station_idx < M inside the loop

Source Code

def solve():
    N, M, K = map(int, input().split())
    D = list(map(int, input().split()))
    
    stations = []
    for _ in range(M):
        P, S = map(int, input().split())
        stations.append((P, S))
    
    # Current battery charge
    battery = K
    
    # Index for charging stations
    station_idx = 0
    
    for i in range(N):
        # Check if there's a charging station before traveling section i+1
        # Before section i+1 = between section i and section i+1
        # When P_j = i, there's a station between section i and section i+1
        # Since sections are 1-indexed, check P_j = i before traveling section i+1
        
        # i is 0-indexed, section numbers are 1-indexed
        # Traveling section i (0-indexed) = traveling section i+1 (1-indexed)
        # Station before section i+1 (1-indexed) has P_j = i (1-indexed)
        
        # There are no stations before section 1, so skip before the first section
        # Before traveling section i+1 (1-indexed), check stations at position P_j = i
        
        if i > 0:
            # After finishing section i (1-indexed, i.e., D[i-1]),
            # before traveling section i+1 (1-indexed, i.e., D[i])
            # Check station position P_j = i (1-indexed)
            while station_idx < M and stations[station_idx][0] == i:
                P, S = stations[station_idx]
                # Choose whether to exchange battery
                # Exchanging sets battery to S
                if S > battery:
                    battery = S
                station_idx += 1
        
        # Travel section i+1 (1-indexed)
        # Need battery >= 1 before traveling
        if battery < 1:
            print("No")
            return
        
        # After traveling, battery decreases by D[i]
        battery -= D[i]
        
        # Even if battery becomes 0 or less, it's OK if it's at least 1 before the next section
        # However, after finishing the last section, it doesn't matter
    
    # All sections completed
    # Even if battery is 0 or less after traveling, all sections are complete so it's OK
    print("Yes")

solve()

---

This editorial was generated by claude4.5opus.