Overview

A problem where Takahashi consumes stamina while mountain climbing, and the stamina consumption changes depending on whether he is exhausted or not. Each time he passes through a section, his stamina decreases, and if he becomes exhausted, it decreases even more. He can recover at mountain huts, but even if he recovers after becoming exhausted, the exhausted state does not revert. Find his final remaining stamina.

Analysis

This problem can be solved by simulating each section in order. The key points are as follows:

• Managing the exhausted state: Once stamina drops to \(0\) or below at any point, consumption is doubled from that point onward. This can be managed with a flag.
• Mountain hut positions and recovery processing: We want to efficiently check whether there is a mountain hut after passing through each section. Storing them in a list would require a linear search each time, which is slow. Using a dictionary (hash map) allows fast access.
• Handling overflow and negative stamina: Stamina can become negative, and there is no upper limit, so simple addition and subtraction suffice.

A naive approach (e.g., linearly searching the mountain hut list each time) would take \(O(N \times M)\) in the worst case, which would result in TLE given the large constraints. To avoid this, we store the mountain hut information in a dictionary beforehand, allowing \(O(1)\) access at each step.

Algorithm

1. Read the input and store the mountain hut information in a pos -> recovery dictionary.
2. Initialize stamina stamina with the initial value \(S\), and initialize the flag tired indicating whether the climber is exhausted to False.
3. For each section \(i = 1, 2, ..., N\), do the following in order:
   • Get the current difficulty \(D_i\).
   • Decrease stamina by \(D_i\) if not exhausted, or by \(2 \times D_i\) if exhausted.
   • After decreasing, if not yet exhausted and stamina is \(0\) or below, set tired = True.
   • If there is a mountain hut right after passing section \(i\), add its recovery amount to stamina.
4. Output the final stamina.

Complexity

• Time complexity: \(O(N + M)\)
  (Both input reading and processing of each section/mountain hut are linear)
• Space complexity: \(O(M)\)
  (For managing mountain hut information in a dictionary)

Implementation Notes

• Mountain hut positions are given in 1-indexed input, but sections may be processed in 0-indexed fashion, so care is needed (in the code, matching is done with i+1).

• sys.stdin.read is used for fast input reading.

• The exhaustion check must be performed after stamina consumption (consume first, then check).

• Mountain hut information may not be sorted, so it is convenient to store it in a dictionary beforehand.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    S = int(data[idx])
    idx += 1
    
    D = [int(data[idx + i]) for i in range(N)]
    idx += N
    
    # 山小屋情報を辞書で管理: pos -> recovery
    huts = {}
    for _ in range(M):
        p = int(data[idx])
        idx += 1
        r = int(data[idx])
        idx += 1
        huts[p] = r
    
    stamina = S
    tired = False
    
    for i in range(N):
        d = D[i]
        # 1. 体力消費
        if not tired:
            stamina -= d
        else:
            stamina -= 2 * d
        
        # 2. バテ判定
        if stamina <= 0 and not tired:
            tired = True
        
        # 3. 回復（山小屋）
        # 区間 i+1 を通過した直後（0-indexed では i）に山小屋があれば回復
        if (i + 1) in huts:
            stamina += huts[i + 1]
    
    print(stamina)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.