Overview

A slime fights monsters in order, absorbing those whose strength is less than or equal to its own to grow stronger. Find the final strength.

Analysis

The slime starts with strength \(W\) and encounters monsters as it proceeds through rooms in order.
If a monster’s strength is less than or equal to the slime’s current strength, the slime absorbs it, adding the monster’s strength to its own.
Otherwise, the slime ignores the monster and moves on to the next one.

This process may seem simple at first glance, and with the number of monsters \(N\) being at most \(2 \times 10^5\), no special optimizations are needed even with a straightforward simulation. However, it is worth noting that since the slime’s strength does not grow exponentially, once it fails to absorb a monster, it may be unable to absorb any subsequent monsters either.

That said, for this problem, a simple simulation with the logic “absorb every monster that can be absorbed” is sufficient, so no particular optimization is necessary.
In other words, it is enough to process each monster from the beginning in order, absorbing it if the current strength is greater than or equal to the monster’s strength.

Algorithm

1. Read the slime’s initial strength \(W\).
2. Read each monster’s strength \(V_i\) in order and perform the following:
   • If the slime’s current strength is greater than or equal to \(V_i\), add \(V_i\) to the slime’s strength.
3. Output the slime’s final strength.

This can be implemented with a simple loop, and no advanced algorithms such as sorting or binary search are required.

Example

Input:

5 10
15 8 20 3 12

Initial state: slime’s strength = 10
- Room 1 (monster 15) → cannot absorb → strength: 10
- Room 2 (monster 8) → absorb → strength: 18
- Room 3 (monster 20) → cannot absorb → strength: 18
- Room 4 (monster 3) → absorb → strength: 21
- Room 5 (monster 12) → absorb → strength: 33

Output: 33

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (for storing the list of monsters)

Implementation Notes

• Iterate through the monster array from the beginning, adding only those that satisfy the condition.

• Choosing meaningful variable names improves code readability (e.g., slime_strength).

• Using map(int, input().split()) when reading input into a list allows for efficient parsing.

  Source Code

N, W = map(int, input().split())
V = list(map(int, input().split()))

slime_strength = W
for v in V:
    if v <= slime_strength:
        slime_strength += v

print(slime_strength)

---

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