Overview

This is a problem where we simulate the process of a slime progressing through rooms in order, absorbing monsters whose strength is less than or equal to its own, and growing stronger.

Analysis

The key point in this problem is that the slime progresses through rooms in order from room 1 to room N.

Key Observations

• The order in which the slime visits rooms is fixed (room 1 → room 2 → … → room N)
• The decision of “whether to absorb or not” at each room is determined solely by comparing the slime’s current strength with the monster’s strength
• The strength of an absorbed monster is added to the slime’s strength, affecting all subsequent decisions

Is a Straightforward Approach Sufficient?

This problem can be solved by simply examining each room in order. No special algorithm is needed.

Example: For \(N=4\), \(W=5\), \(V=[3, 10, 2, 4]\): 1. Room 1: Monster’s strength 3 ≤ Slime’s strength 5 → Absorb! Slime’s strength = 5 + 3 = 8 2. Room 2: Monster’s strength 10 > Slime’s strength 8 → Cannot absorb. Slime’s strength remains 8 3. Room 3: Monster’s strength 2 ≤ Slime’s strength 8 → Absorb! Slime’s strength = 8 + 2 = 10 4. Room 4: Monster’s strength 4 ≤ Slime’s strength 10 → Absorb! Slime’s strength = 10 + 4 = 14

The final strength of the slime is 14.

Algorithm

1. Initialize the slime’s strength to the initial value \(W\)
2. Repeat the following for each room from room 1 to room N:
   • If the monster’s strength \(V_i\) is less than or equal to the slime’s current strength, add \(V_i\) to the slime’s strength
   • Otherwise, do nothing
3. Output the final strength of the slime

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

As shown, simply implementing the problem statement directly yields the correct answer.

Complexity

• Time complexity: \(O(N)\)
  • Each room is visited once, and constant-time processing is performed at each
• Space complexity: \(O(N)\)
  • The size of the array \(V\) storing the monsters’ strengths

Implementation Notes

• Beware of overflow: Since \(W\) and \(V_i\) can be up to \(10^9\), and up to \(2 \times 10^5\) monsters may be absorbed, the final strength can reach approximately \(2 \times 10^{14}\). In Python, there is no need to worry about integer overflow, but in C++ and similar languages, you need to use the long long type.

• Equality in the condition: The problem states “absorb if the strength is less than or equal to,” so make sure to include the equality sign with v <= strength.

  Source Code

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

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

print(strength)

---

This editorial was generated by claude4.5opus.