Overview

Process rooms from left to right, following the rule “defeat if possible, skip if not,” and compute the total penalty based on the number of skips.

Analysis

The key point of this problem is that there is no choice involved. At each room, Takahashi can only take one of two actions:

• If current stamina \(stamina\) is at least \(H_i\), he must defeat the enemy (stamina updates to \(stamina \leftarrow stamina - H_i + P_i\))
• If less than \(H_i\), he cannot defeat it and must skip (stamina stays the same, and the skip count increases)

In other words, this is not a problem where you “optimize which rooms to defeat/skip” — it is a problem where simply simulating determines the result uniquely.

Even though it may look straightforward, all you need to do is perform a condition check and stamina update for each room, which is fast enough even for \(N \le 2\times 10^5\). Conversely, unnecessarily considering DP or search not only complicates the implementation but may also slow things down with unnecessary computation.

Concrete example: - \(S=10\) - Room 1 \((H_1,P_1)=(7,3)\): \(10\ge 7\) so defeat → stamina \(10-7+3=6\) - Room 2 \((H_2,P_2)=(8,0)\): \(6<8\) so skip → skip count \(+1\) The final answer is skip count \(\times C\).

Algorithm

1. Initialize stamina \(stamina \leftarrow S\) and skip count \(skips \leftarrow 0\).
2. Process rooms in order from \(i=1\) to \(N\).
   • If \(stamina \ge H_i\), defeat the enemy and update \(stamina \leftarrow stamina - H_i + P_i\).
   • Otherwise, skip and update \(skips \leftarrow skips + 1\).
3. Output \(skips \times C\).

Complexity

• Time complexity: \(O(N)\) (each room is processed once)
• Space complexity: \(O(1)\) (excluding input storage, only a constant number of variables are used)

Implementation Notes

• Since \(N\) can be large, in Python it is faster to read all input at once using sys.stdin.buffer.read() and process it as a sequence of integers.

• The penalty is “number of skips × \(C\),” so you could add the penalty each time a skip occurs, but multiplying at the end is clearer.

• Stamina and penalty values can be on the order of \(10^9\), but Python integers do not overflow, so they can be handled without worry.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, S, C = data[0], data[1], data[2]
    stamina = S
    skips = 0
    idx = 3
    for _ in range(N):
        H = data[idx]
        P = data[idx + 1]
        idx += 2
        if stamina >= H:
            stamina = stamina - H + P
        else:
            skips += 1
    print(skips * C)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.