Overview

This is a problem where you traverse N sections in order to reach the summit, consuming stamina along the way and recovering at mountain huts. You need to determine the final remaining stamina while considering changes in exhaustion state.

Analysis

In this problem, for each section traversed, the following 3 steps must be processed in order: 1. Consume stamina according to the current state (whether exhausted or not) 2. If stamina drops to 0 or below and not yet exhausted, transition to the exhausted state 3. If there is a mountain hut, recover

The key points are: once exhausted, the state is never removed; the order of stamina consumption and exhaustion check matters; and recovery is performed without an upper limit. This can be solved by straightforward simulation, but since the input size can be up to 200,000, an efficient implementation is necessary.

Algorithm

1. Read input data and store each section’s difficulty and each position’s recovery amount in arrays
2. Set initial stamina S and exhaustion state flag (initial value false)
3. Process sections 1 through N in order:
   • Consume stamina according to exhaustion state (not exhausted: \(D_i\), exhausted: \(2 \times D_i\))
   • If stamina is 0 or below and not yet exhausted, set the exhaustion flag to true
   • If the current section is not the last one, add the corresponding recovery amount
4. Output the final stamina

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(N + M)\) for reading input
  • \(O(N)\) for the main loop
• Space complexity: \(O(N)\)
  • \(O(N)\) each for the difficulty array and recovery amount array

Implementation Notes

• Recovery amounts are stored in the array using addition, since multiple mountain huts may exist at the same section

• Once the exhaustion state becomes true, it is never changed back

• No recovery is performed at the last section (i = N)

• Input data reading is optimized using iterators

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    N = int(next(it)); M = int(next(it)); S = int(next(it))
    D = [0] * (N+1)
    for i in range(1, N+1):
        D[i] = int(next(it))
    
    recoveries = [0] * (N+1)
    for _ in range(M):
        p = int(next(it)); r = int(next(it))
        recoveries[p] += r
    
    current_health = S
    is_bate = False
    
    for i in range(1, N+1):
        if not is_bate:
            current_health -= D[i]
        else:
            current_health -= 2 * D[i]
            
        if current_health <= 0 and not is_bate:
            is_bate = True
            
        if i < N:
            current_health += recoveries[i]
            
    print(current_health)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.