Overview

This is a problem where you visit dungeon rooms in order, determine whether you can defeat each monster based on your current health, and calculate a penalty based on the number of rooms skipped.

Analysis

The rules of the problem are simple: at each room, if your current health is at least the monster’s strength \(H_i\), you defeat it and update your health; otherwise, you skip the room and add a penalty of \(C\). The key point is that after defeating a monster, your health is updated to \(\text{current health} - H_i + P_i\). This problem can be solved by simply performing condition checks and state updates at each step. Although the constraint \(N \leq 2 \times 10^5\) is large, since the processing at each step can be done in constant time, a linear-time algorithm is sufficient.

Algorithm

1. Start with initial health \(S\) and penalty \(0\).
2. Process each room \(i\) in order:
   • If the current health is at least \(H_i\), update health to \(\text{current health} - H_i + P_i\).
   • Otherwise, add \(C\) to the penalty (skip).
3. Output the total penalty after processing all rooms.

This algorithm straightforwardly simulates the process exactly as specified in the problem. Since health is updated at each step, the decision for the next room is based on the updated health.

Complexity

• Time complexity: \(O(N)\)
  • Because each of the \(N\) rooms is processed exactly once.
• Space complexity: \(O(N)\)
  • Because the arrays \(H\) and \(P\) need to be stored.

Implementation Notes

• For input reading, efficiency is achieved by reading all data at once before processing.

• The implementation is simple: just maintain a variable for the current health, update it, and perform a conditional branch at each room.

• There is no need to worry about integer overflow (since Python integers have arbitrary precision).

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    S = int(data[1])
    C = int(data[2])
    H = []
    P = []
    index = 3
    for i in range(n):
        H.append(int(data[index]))
        P.append(int(data[index+1]))
        index += 2
        
    current_health = S
    penalty = 0
    
    for i in range(n):
        if current_health >= H[i]:
            current_health = current_health - H[i] + P[i]
        else:
            penalty += C
            
    print(penalty)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.