Overview

This is a problem where a slime visits \(N\) rooms in order, absorbing monsters whose strength is “less than or equal to” its own strength, growing along the way, and we need to determine the slime’s final strength.

Analysis

The key point of this problem is that the order in which the slime moves through rooms is “fixed from room 1 to room \(N\)”.

The slime’s strength increases each time it absorbs a monster. Whether the slime can absorb the monster in room \(i\) depends on how many monsters it has absorbed and how strong it has become in the previous rooms (rooms \(1\) through \(i-1\)).

However, since the slime always visits rooms in increasing order of their number, we can arrive at the correct answer by simply performing a straightforward simulation with the following steps:

1. Maintain the slime’s current strength in a variable (current_strength).
2. Go through rooms \(1\) to \(N\) in order.
3. If the monster’s strength \(V_i\) in that room is less than or equal to current_strength, add \(V_i\) to current_strength.
4. Otherwise, do nothing.

Checking the constraints, the number of rooms \(N\) is at most \(2 \times 10^5\). This simulation only performs one comparison and one addition per room, so the overall time complexity is proportional to \(N\), which is well within the time limit.

Algorithm

1. Read the slime’s initial strength \(W\) and assign it to the variable current_strength representing its current strength.
2. Read the list \(V\) of monster strengths.
3. Using a loop (for statement), repeat the following process for rooms \(i = 0\) to \(N-1\):
   • If \(V_i \le \text{current\_strength}\):
     • current_strength = current_strength + \(V_i\)
4. Output current_strength after the loop ends.

Complexity

• Time Complexity: \(O(N)\)
  • We loop through each of the \(N\) rooms once, performing a comparison and addition each time.
• Space Complexity: \(O(N)\)
  • This is the complexity for storing the monster strengths in memory as a list \(V\).

Implementation Notes

• Handling large numbers: The slime’s final strength could have an initial value of \(10^9\) with up to \(2 \times 10^5\) values of \(10^9\) added to it, resulting in a value of approximately \(2 \times 10^{14}\). In Python, there is no limit on integer size, so this is not an issue. However, when using languages like C++, you need to use a 64-bit integer type (long long).

• Speeding up input: Since \(N\) can be as large as \(2 \times 10^5\), in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() or similar methods.

  Source Code

import sys

def solve():
    # 入力をすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 部屋の数, W: スライムの初期の強さ
    n = int(input_data[0])
    current_strength = int(input_data[1])
    
    # V: 各部屋のモンスターの強さ
    v = input_data[2:]
    
    # 各部屋を順番に回る
    for i in range(n):
        monster_strength = int(v[i])
        # モンスターの強さがスライムの現在の強さ以下なら吸収する
        if monster_strength <= current_strength:
            current_strength += monster_strength
            
    # 最終的なスライムの強さを出力
    print(current_strength)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.