Overview

This is a simulation problem where you visit monsters from left to right, push monsters you can’t defeat onto a stack to deal with later, and each time you defeat a monster, you check whether you can chain-defeat monsters from the top of the stack.

Analysis

Understanding the Problem Structure

Takahashi starts with attack power \(h = 0\) and visits monsters from left to right. For each monster:

• If he cannot defeat it (\(D_i > h\)): Push it onto the top of the stack (postpone it)
• If he can defeat it (\(D_i \leq h\)): Defeat it, set \(h \leftarrow h + D_i\), gold \(+V_i\). Then, chain-defeat monsters from the top of the stack as long as possible.

The key point is that the stack is LIFO (Last In, First Out), so the most recently postponed monster is the first candidate for a retry. You cannot skip monsters in the middle of the stack.

Complexity Analysis

At first glance, it might seem like the while loop checking the stack after defeating each monster results in a double loop of \(O(N^2)\).

However, each monster is pushed onto the stack at most once and popped from the stack at most once. This means the total number of pop operations inside the while loop across the entire execution is at most \(N\). This is known as “amortized analysis,” and the overall complexity is \(O(N)\).

Concrete Example

For example, suppose \(N = 4\) with the following monsters:

Monster	\(D_i\)	\(V_i\)
1	0	10
2	5	20
3	3	15
4	0	5

• Monster 1: \(D_1 = 0 \leq h = 0\) → Defeat it. \(h = 0, \text{gold} = 10\). Stack is empty, so no chain processing.
• Monster 2: \(D_2 = 5 > h = 0\) → Postpone. Stack: \([(5, 20)]\)
• Monster 3: \(D_3 = 3 > h = 0\) → Postpone. Stack: \([(5, 20), (3, 15)]\)
• Monster 4: \(D_4 = 0 \leq h = 0\) → Defeat it. \(h = 0, \text{gold} = 15\). Top of stack is \((3, 15)\), \(3 > 0\) so chain ends.
• Final chain processing: Top of stack is \((3, 15)\), \(3 > 0\) → Cannot defeat, done.

Final result: Gold \(15\), 2 monsters remain in the stack.

Algorithm

1. Prepare \(h = 0\) (attack power), \(\text{gold} = 0\) (gold held), and an empty stack.
2. Process each monster in order \(i = 1, 2, \ldots, N\):
   • If \(D_i > h\), push \((D_i, V_i)\) onto the stack.
   • If \(D_i \leq h\), defeat it: \(h += D_i\), \(\text{gold} += V_i\). Then, chain-defeat monsters from the top of the stack as long as possible.
3. After visiting all monsters, perform one final chain-defeat processing from the top of the stack.
4. Output \(\text{gold}\).

Complexity

• Time complexity: \(O(N)\) (each monster’s push/pop to the stack occurs at most \(N\) times total)
• Space complexity: \(O(N)\) (the stack may contain up to \(N\) monsters)

Implementation Notes

• Using Python’s list with append for push and pop() for removing the top element makes stack implementation straightforward.

• Using sys.stdin.buffer.read() to read all input at once enables fast input processing even in Python.

• The attack power \(h\) can reach up to \(N \times 10^9 \approx 2 \times 10^{14}\), but in Python there is no need to worry about integer overflow (in C++ etc., long long would be required).

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    
    h = 0
    gold = 0
    stack = []  # list of (D, V), top is end
    
    for i in range(N):
        D = int(input_data[idx]); idx += 1
        V = int(input_data[idx]); idx += 1
        
        if D > h:
            stack.append((D, V))
        else:
            gold += V
            h += D
            # 後回し解消処理
            while stack and stack[-1][0] <= h:
                d, v = stack.pop()
                gold += v
                h += d
    
    # 最後にもう一度後回し解消処理
    while stack and stack[-1][0] <= h:
        d, v = stack.pop()
        gold += v
        h += d
    
    print(gold)

main()

---

This editorial was generated by claude4.6opus-thinking.