Overview

The result of each battle with a monster is uniquely determined by your current health at that point.
Therefore, you can find the answer by simply simulating from the \(1\)st monster in order and counting the number of monsters defeated.

Analysis

The key point of this problem is that there are no choices in each battle.

For monster \(i\):

• If your health is at least \(H_i\), you defeat it and your health decreases by \(H_i\)
• If your health is less than \(H_i\), you cannot defeat it and your health increases by \(H_i\)

Since these rules are fixed, what happens at each step is completely unique.
In other words, there are no elements like “choosing which monster to defeat” or “taking a different action later.”

For example, with initial health \(P=10\) and monsters \([4,7,3]\):

1. First monster \(4\): \(10 \ge 4\), so you can defeat it
   \(\rightarrow\) Health becomes \(10-4=6\), defeat count is \(1\)
2. Next monster \(7\): \(6 < 7\), so you cannot defeat it
   \(\rightarrow\) Health becomes \(6+7=13\)
3. Next monster \(3\): \(13 \ge 3\), so you can defeat it
   \(\rightarrow\) Health becomes \(13-3=10\), defeat count is \(2\)

Therefore, the answer is \(2\).

On the naive approach

In this problem, there is no need to consider complex methods like exhaustive search or dynamic programming.
This is because the action at each step is fixed, and there are no branches.

Also, since the order of monsters is fixed, attempting to rearrange or batch-process them will lead to wrong answers.
Ultimately, there is no correct method other than processing from the beginning in order, so directly simulating is the most natural and efficient approach.

Algorithm

Process with the following steps:

1. Set the current health to hp = P
2. Set the defeat count ans = 0
3. Iterate through the monsters from the beginning in order
   • If hp >= H_i:
     • hp -= H_i
     • ans += 1
   • Otherwise:
     • hp += H_i
4. Output ans at the end

This process is performed only once for each monster.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

※ The space complexity is \(O(N)\) because the implementation stores the array of monster strengths.
The additional working variables used are \(O(1)\).

Implementation Notes

• Even if your health becomes exactly \(0\), the process continues.

• Be careful not to overlook that “health increases when you cannot defeat a monster.”

• Since the constraints are large with \(N \le 5 \times 10^5\), using sys.stdin.buffer.read() for input is faster.

• Although health repeatedly increases and decreases, Python’s integer type can handle this safely as-is.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, P = data[0], data[1]
    H = data[2:2 + N]

    hp = P
    ans = 0

    for h in H:
        if hp >= h:
            hp -= h
            ans += 1
        else:
            hp += h

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.