Overview

This is a simulation problem where a slime absorbs monsters in order, absorbing only monsters whose strength is less than or equal to the slime’s current strength and adding their strength to its own.

Analysis

This problem is a straightforward simulation where the slime moves through each room in order, absorbing monsters whose strength is less than or equal to its current strength. The key point is that the decision of whether absorption is possible is based on the “slime’s current strength.” In other words, since the slime’s strength increases with each absorption, there is a possibility of absorbing stronger monsters later on.

A naive approach of processing each room in order is sufficient. This is efficient enough given the problem’s constraints, because the maximum value of \(N\) is \(2 \times 10^5\), and a simple loop can compute the result in \(O(N)\).

Algorithm

The algorithm is very simple: 1. Set the initial strength \(W\) to current 2. Process each room’s monster strength \(V_i\) in order 3. For each monster, if \(V_i \leq\) current, add \(V_i\) to current 4. Output current after processing all rooms

This algorithm leverages the property that the slime’s strength is monotonically increasing. Since the strength of each absorbed monster is permanently added to the slime, it becomes progressively easier to absorb subsequent monsters.

Complexity

• Time complexity: \(O(N)\)
  • Because each of the \(N\) monsters is processed exactly once
• Space complexity: \(O(N)\)
  • For the array storing the monsters’ strengths

Implementation Notes

Key points for implementation are as follows: - Be mindful of the input value ranges (\(W\) and \(V_i\) can be up to \(10^9\)) - Only integer arithmetic is needed - When updating the current strength, only addition is performed; subtraction never occurs - Reading all input data at once can improve efficiency

Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    w = int(data[1])
    V = list(map(int, data[2:2+n]))
    
    current = w
    for v in V:
        if v <= current:
            current += v
            
    print(current)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.