Overview

This is a problem where you follow the given rules — “defeat if possible / push onto the stack if not” — processing monsters in order, then at the end defeat as many as possible from the stack, and compute the total reward.

Analysis

The key point of this problem is that there are no choices to make — the procedure is completely determined. Therefore, this is not an “optimization” problem; you can obtain the answer by accurately simulating the rules.

However, there are some caveats:

• Each time you defeat a monster, a “deferred resolution process” runs, which may allow you to chain-defeat monsters on the stack.
• If you implement this naively — for example, searching through the entire stack for defeatable monsters — you end up scanning the stack contents repeatedly, which can be \(O(N^2)\) in the worst case and result in TLE.

However, the “deferred resolution process” in this problem: - Only looks at the top of the stack - If defeated, pop it, attack power increases, then check the new top

This is exactly LIFO (try the most recently pushed first) behavior. Therefore, using a stack (end of an array):

• If you can’t defeat it, push
• If you can defeat it, defeat it, then while “pop as long as the top can be defeated”

This alone perfectly reproduces the process as described in the rules.

Concrete example: - When \(h=3\), suppose the deferred stack has strengths [10, 4, 2] from bottom to top (rightmost is the top). - Top 2 can be defeated → defeat it, \(h=5\) - New top 4 can also be defeated → defeat it, \(h=9\) - New top 10 cannot be defeated → stop here This behavior of “only checking from the top” is crucial.

Algorithm

Maintain the following variables:

• Current attack power \(h\) (initially \(0\))
• Total gold gold (initially \(0\))
• Deferred stack stack (elements are (D, V))

The process is as follows:

1. Process \(i=1..N\) in order.
2. If \(D_i > h\), you cannot defeat it, so stack.append((D_i, V_i)).
3. If \(D_i \le h\), defeat it:
   • gold += V_i
   • h += D_i
   • Immediately after, run the deferred resolution process:
     • while stack is not empty and stack[-1].D <= h:

          - `pop` and defeat it (update `gold` and `h`)
       

4. After visiting all monsters, run the same while one more time to defeat as many as possible from the stack.
5. Remaining monsters in the stack cannot be defeated, so ignore them and output gold.

This method is a direct translation of the problem’s procedure into code.

Complexity

• Time complexity: \(O(N)\) Each monster is pushed at most once and popped at most once. Even though there is a while loop, the total number of pop operations is at most \(N\), so the overall time is linear (amortized complexity).
• Space complexity: \(O(N)\) In the worst case, all monsters are deferred, and \(N\) elements are pushed onto the stack.

Implementation Notes

• In Python, using append / pop on a list handles the stack efficiently (end operations are \(O(1)\)).

• The “deferred resolution process” must always be in the form while stack and stack[-1][0] <= h:, only looking at the top and chaining the processing.

• Since the input can be up to \(2\times 10^5\), using fast input like sys.stdin.buffer.read() is recommended to be safe.

• Even when \(D_i=0\), “defeat if possible” works without issues (attack power doesn’t increase, but the reward is still added).

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    idx = 1

    h = 0
    gold = 0
    stack = []  # (D, V)

    for _ in range(n):
        d = int(data[idx]); v = int(data[idx + 1]); idx += 2
        if d > h:
            stack.append((d, v))
        else:
            gold += v
            h += d
            while stack and stack[-1][0] <= h:
                d2, v2 = stack.pop()
                gold += v2
                h += d2

    while stack and stack[-1][0] <= h:
        d2, v2 = stack.pop()
        gold += v2
        h += d2

    sys.stdout.write(str(gold))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.