Overview

Takahashi explores \(N\) rooms arranged in a line from left to right in order. If his stamina is insufficient, he skips the room and pays a penalty. We need to find the total penalty after processing all rooms.

Analysis

In this problem, Takahashi visits rooms from left to right and determines the action (defeat or skip) for each monster. For each monster:

• If the current stamina \(current\_hp\) is greater than or equal to the monster’s strength \(H_i\), he defeats the monster.
  • Stamina is updated to \(current\_hp = current\_hp - H_i + P_i\).
• Otherwise, he skips the room and adds a penalty of \(C\).

The key point is that rooms are “processed in order” — there is no going back or making choices, so this can be solved with a straightforward simulation.

There is nothing particularly difficult about the naive approach; you simply process the input sequentially. However, depending on how input is read, you may get TLE. In Python specifically, using input() is slow, so you need to use a faster input method (e.g., sys.stdin.read).

Algorithm

1. Read all input at once and obtain \(N\), \(S\), \(C\), and each room’s \(H_i\), \(P_i\).
2. Set initial stamina \(current\_hp = S\) and total penalty \(penalty = 0\).
3. For each room from left to right, do the following:
   • If the current stamina is at least \(H_i\):
     • \(current\_hp \leftarrow current\_hp - H_i + P_i\)
   • Otherwise:
     • \(penalty \leftarrow penalty + C\)
4. Output the final value of \(penalty\).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• In Python, when handling large amounts of input, use sys.stdin.read for speedup.

• Since input is read all at once as a string, it needs to be properly split and type-converted.

• Pay attention to the range of int types, as particularly large values (e.g., on the order of \(10^9\)) may be involved.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    S = int(data[1])
    C = int(data[2])
    
    H = [0] * N
    P = [0] * N
    
    for i in range(N):
        H[i] = int(data[3 + 2*i])
        P[i] = int(data[4 + 2*i])
    
    penalty = 0
    current_hp = S
    
    for i in range(N):
        if current_hp >= H[i]:
            current_hp -= H[i]
            current_hp += P[i]
        else:
            penalty += C
    
    print(penalty)

if __name__ == "__main__":
    main()

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