Imp 2

1. Representing a strategy as an order

If the imp does not cast a spell after a purchase, the game ends immediately. Therefore, the only continuation branch is that the just-bought item is destroyed. A strategy can consequently be represented by an order of distinct boxes.

Fix a positive target profit $x$. Since the imp may destroy the first $k$ bought items, guaranteeing an obtained item requires planning $k+1$ boxes. For an order $p_1,p_2,\ldots,p_{k+1}$, if the first surviving item is $p_i$, the required condition is

$$\sum_{j=1}^{i} c_{p_j} \le v_{p_i}-x$$

for every $1 \le i \le k+1$.

Profit $0$ is always available by leaving immediately.

2. Scheduling reduction

For a fixed $x$, create one job for each box with processing time $c_i$ and deadline $v_i-x$. The condition above asks for at least jobs that can all finish by their deadlines.

3. Maximum number of on-time jobs

Process jobs in nondecreasing deadline order. Insert each processing time into a max-heap and add it to the current total. If the total exceeds the current deadline, remove the largest processing time.

After every prefix, the heap contains a maximum-cardinality feasible subset, and among such subsets it has minimum total processing time. Removing the longest selected job is exactly the exchange that preserves this invariant.

The target $x$ is feasible if and only if the final heap size is at least $k+1$.

Because deadlines are $v_i-x$, their relative order is the same as the order of $v_i$ for every $x$, so the items need to be sorted only once.

4. Binary search

Feasibility is monotone in $x$. The answer lies between $0$ and $1\ 000\ 000$, so binary-search this range.

A feasibility check costs $O(n\log n)$. The total time complexity is

$$O(n\log n\log 1\ 000\ 001),$$

with $O(n)$ memory.

Solution written by GPT5.6