Overview

This is a problem where you visit \(N\) rooms in order, following the rule: if your current stamina is at least the monster’s strength, you “fight”; otherwise, you “skip and pay a penalty.” You simulate this process and find the total penalty amount at the end.

Analysis

The most important point in this problem is that the rule “always defeat a monster if you can, and only skip if you cannot” is fixed. Since Takahashi has no choice to, say, deliberately skip a monster he could defeat, we can arrive at the correct answer simply by simulating from the leftmost room in order using conditional branching (if statements).

Points to be careful about: - Large values: Stamina \(S\), penalty \(C\), and monster strengths \(H_i\) can be as large as \(10^9\). The total penalty can be \(N \times C\), potentially reaching around \(2 \times 10^{14}\). Python natively supports arbitrary-precision integers, so you can compute without worrying about overflow. - Computational complexity: Since the number of rooms \(N\) can be up to \(2 \times 10^5\), each room must be processed in \(O(1)\) time, keeping the overall complexity at \(O(N)\).

Algorithm

We use a simple simulation (sequential processing).

1. Initialize the current stamina as \(current\_stamina = S\) and the total penalty as \(total\_penalty = 0\).
2. For rooms \(i = 1, 2, \dots, N\), perform the following operations in order:
   • If \(current\_stamina \geq H_i\) (the monster can be defeated):
     • Consume stamina, then recover: \(current\_stamina = current\_stamina - H_i + P_i\)
   • Otherwise (the monster cannot be defeated):
     • Add the penalty: \(total\_penalty = total\_penalty + C\)
     • Stamina does not change.
3. After processing all rooms, output \(total\_penalty\).

Complexity

• Time complexity: \(O(N)\)
  • We traverse the \(N\) rooms once, performing constant-time comparisons and arithmetic at each room, so the time is proportional to the number of rooms.
• Space complexity: \(O(N)\)
  • If all input values are read into lists, memory proportional to \(N\) is used.

Implementation Notes

• Fast I/O: When handling input of size \(N = 2 \times 10^5\) in Python, repeatedly calling input() can be slow. By reading all input at once using sys.stdin.read().split() and processing it with an iterator (iter()), data can be retrieved efficiently.

• Faithful simulation of the process: Directly translate the procedure described in the problem statement — “subtract \(H_i\), then add \(P_i\)” — into code. Due to the conditional branching, stamina never becomes negative during the process. However, note that the recovery amount \(P_i\) may cause stamina to exceed the initial value \(S\) (since there is no upper limit specified in this problem, you can simply compute as-is without issue).

  Source Code

import sys

def solve():
    """
    ダンジョン探索の問題を解く関数です。
    各部屋のモンスターを順番に判定し、体力が足りれば倒し、
    足りなければスキップして罰金を加算します。
    """
    
    # 標準入力からすべての入力を読み込み、空白や改行で分割してトークンのリストを作成します。
    # 大量の入力を効率的に処理するために sys.stdin.read().split() を使用します。
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は何もせず終了します。
    if not input_data:
        return
    
    # トークンを順番に取り出すためのイテレータを作成します。
    it = iter(input_data)
    
    # 最初の3つの値（部屋の数 N、初期体力 S、スキップの罰金 C）を取得します。
    try:
        n = int(next(it))
        s = int(next(it))
        c = int(next(it))
    except (StopIteration, ValueError):
        return
    
    # 現在の体力を初期体力 S で初期化します。
    current_stamina = s
    # 罰金の合計額を 0 で初期化します。
    total_penalty = 0
    
    # N 個の部屋を順番に処理します。
    for _ in range(n):
        try:
            # 各モンスターの強さ H と倒した後の回復量 P を取得します。
            h = int(next(it))
            p = int(next(it))
        except (StopIteration, ValueError):
            break
            
        # 現在の体力がモンスターの強さ H 以上であれば倒すことができます。
        if current_stamina >= h:
            # モンスターを倒すと体力が H 減り、その後 P 回復します。
            current_stamina = current_stamina - h + p
        else:
            # 体力が足りない場合は部屋をスキップし、罰金 C を支払います。
            # このとき体力は変化しません。
            total_penalty += c
            
    # 全ての部屋を処理した後の罰金の合計額を出力します。
    print(total_penalty)

if __name__ == "__main__":
    # プログラムの実行を開始します。
    solve()

This editorial was generated by gemini-3-flash-thinking.