Overview

This is a problem where you proceed through rooms in order, absorbing only monsters whose strength is less than or equal to your current strength to increase it, and you need to find the final strength of the slime.

Analysis

The key point of this problem is that the slime’s behavior is completely fixed to “visiting rooms \(1\) through \(N\) in order.” This means the only decision needed at each room is the following check:

• If \(V_i \leq\) current strength, absorb it and increase strength by \(+ V_i\)
• Otherwise, nothing happens (pass through)

Here, actions like “going back later to absorb monsters that couldn’t be absorbed” are not possible, nor can the order be changed. Therefore, the processing at each room is determined solely by the current strength at that point, and simply performing a simulation (sequential processing) gives the correct answer.

Rather than being naive, “implementing it exactly as described” is optimal. Unnecessarily adding tricks like searching or sorting will break the condition (fixed order) and cause WA.

Example: - Initial \(W=10\), monsters \([3, 15, 7]\) - \(3 \le 10\) so absorb → \(W=13\) - \(15 > 13\) so cannot absorb → \(W=13\) - \(7 \le 13\) so absorb → \(W=20\) - Answer is \(20\)

Algorithm

1. Initialize the current strength cur with the initial value \(W\).
2. For \(i=1\) through \(N\) in order, examine each monster’s strength \(V_i\).
3. If \(V_i \le cur\), absorb it by setting cur += V_i.
4. Finally, output cur.

This procedure is a simulation that directly reproduces the behavior described in the problem statement.

Complexity

• Time complexity: \(O(N)\) (just examining each monster once)
• Space complexity: \(O(1)\) (excluding the input array, only the current value needs to be maintained)

Implementation Notes

• Since \(N\) can be up to \(2 \times 10^5\), in Python using sys.stdin.buffer.read() to read all input at once is consistently fast and stable.

• The strength can grow large through additions, but Python integers do not overflow, so additions can be performed without concern.

• Note that the condition is \(V_i \le cur\) (including equality).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, W = data[0], data[1]
    V = data[2:2+N]
    cur = W
    for x in V:
        if x <= cur:
            cur += x
    print(cur)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.