Overview

This problem involves visiting monsters from left to right, deciding whether to push them onto a stack or defeat them based on the current attack power, and performing resolution processing on stacked monsters later, to find the total reward obtained.

Analysis

The key points of the problem are the order in which monsters are visited and the LIFO (Last In, First Out) property of the postponement stack. Monsters are visited from left to right, but postponed monsters are pushed onto a stack and resolved later. During this resolution processing, we check from the top of the stack (the most recently pushed monster) and defeat them if the current attack power is sufficient, increasing the attack power accordingly. Naively checking all monsters each time would take \(O(N^2)\) time in the worst case, which is too slow for the constraint \(N \leq 2 \times 10^5\). Therefore, we need to use a stack to process efficiently.

Algorithm

1. Initialize the current attack power \(h\) and total reward \(total\_gold\) to 0, and prepare an empty stack.
2. Process each monster \(i\) from left to right:
   • If \(D_i > h\): Push the monster onto the stack.
   • If \(D_i \leq h\): Defeat the monster, add reward \(V_i\), and increase attack power \(h\) by \(D_i\). Then, as long as the stack is not empty and the strength of the monster on top of the stack is at most \(h\), pop monsters from the stack, defeat them, and update the reward and attack power.
3. After visiting all monsters, perform the resolution processing again on the monsters remaining in the stack (pop and process from the top of the stack as long as they can be defeated with the current attack power).
4. Output the final total reward \(total\_gold\).

In this algorithm, each monster is pushed onto the stack at most once and popped at most once, so the processing is efficient.

Complexity

• Time complexity: \(O(N)\)
  • Each monster is pushed onto the stack once and popped once, so the entire process runs in linear time.
• Space complexity: \(O(N)\)
  • In the worst case, \(N\) monsters are stored on the stack, requiring linear space.

Implementation Notes

• The stack stores pairs of each monster’s strength \(D_i\) and reward \(V_i\).

• The postponement resolution processing is performed twice: immediately after defeating a monster, and after all monsters have been visited.

• For stack operations, a while stack: loop is used to check the top of the stack and keep popping as long as the condition is satisfied.

• For input reading, efficiency is improved by reading all data at once and then processing it.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    D = []
    V = []
    index = 1
    for i in range(n):
        D.append(int(data[index]))
        V.append(int(data[index+1]))
        index += 2
        
    h = 0
    total_gold = 0
    stack = []
    
    for i in range(n):
        if D[i] > h:
            stack.append((D[i], V[i]))
        else:
            total_gold += V[i]
            h += D[i]
            while stack:
                top_d, top_v = stack[-1]
                if top_d <= h:
                    total_gold += top_v
                    h += top_d
                    stack.pop()
                else:
                    break
                    
    while stack:
        top_d, top_v = stack[-1]
        if top_d <= h:
            total_gold += top_v
            h += top_d
            stack.pop()
        else:
            break
            
    print(total_gold)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.