Overview

Visit monsters in order, defeat them and earn rewards if your attack power is sufficient. If not, store them on a stack to process later. Find the total rewards obtained in the end.

Analysis

In this problem, as we visit monsters from left to right, if our attack power is insufficient, we temporarily save them on a stack (LIFO) and later determine whether we can defeat them after our attack power has increased.

The key observation is that in the “deferred processing” step, we need to search for defeatable monsters starting from the top of the stack. In other words, since the stack is a LIFO structure, we need to process monsters in newest-first order, and processing may occur multiple times, so we need to use an efficient data structure.

A naive approach of scanning the entire stack each time would be inefficient, taking \(O(N^2)\) in the worst case, which would result in TLE given the constraint \(N \leq 2 \times 10^5\).

To solve this, we leverage the property that we only need to look at the top of the stack, and implement the stack using Python’s collections.deque, which allows fast additions and removals.

Furthermore, by performing the “deferred processing” each time we visit a monster, we prevent any missed processing, and by performing deferred processing one final time at the end, we can defeat as many monsters remaining in the stack as possible.

Algorithm

1. Process each monster from left to right.
2. If the current attack power \(h\) is at least the monster’s strength \(D_i\), defeat it on the spot, earn reward \(V_i\), and update the attack power.
3. Immediately after defeating a monster, perform “deferred processing”:
   • If the monster on top of the stack can be defeated with the current attack power, pop it from the stack and defeat it (repeat this).
4. If the attack power is insufficient, push that monster onto the stack.
5. After processing all monsters, perform “deferred processing” one more time.
6. Output the total rewards obtained.

Complexity

• Time complexity: \(O(N)\)
  Each monster is pushed onto the stack at most once and popped at most once, so the total is \(O(N)\).
• Space complexity: \(O(N)\)
  The stack stores at most \(N\) monsters.

Implementation Notes

• Store (D, V) tuples on the stack so that we can compare with attack power and retrieve the reward at the same time.

• Implement the deferred processing as a loop that terminates when the stack is empty or the top monster cannot be defeated.

• Be careful not to forget the final processing step (perform deferred processing again after visiting all monsters).

  Source Code

import sys
from collections import deque

input = sys.stdin.read
data = input().split()

N = int(data[0])
monsters = [(int(data[2*i+1]), int(data[2*i+2])) for i in range(N)]

h = 0
total_gold = 0
stack = deque()  # (D, V) のタプルを保持するスタック

for D, V in monsters:
    if D <= h:
        # 倒せる場合
        total_gold += V
        h += D
        
        # 後回し解消処理
        while stack and stack[-1][0] <= h:
            d, v = stack.pop()
            total_gold += v
            h += d
    else:
        # 倒せない場合はスタックに追加
        stack.append((D, V))

# 最後の後回し解消処理
while stack and stack[-1][0] <= h:
    d, v = stack.pop()
    total_gold += v
    h += d

print(total_gold)

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