Monster Game

For a chosen difficulty $x$, every sword with strength at least $x$ becomes just “one usable strike,” and every weaker sword is trash. Brutal, but simple.

Let

$m(x) = \#\{i : a_i \ge x\}.$

With $m(x)$ usable swords, we can only spend them from level $1$ onward. Level $i$ costs $b_i$ swords, so completing the first $k$ levels costs

$p_k = \sum_{i=1}^{k} b_i.$

Therefore, for this $x$, the number of completed levels is the largest $k$ such that

$p_k \le m(x).$

The score is then

$x \cdot k.$

Now the important false assumption to kill: we do not need to binary search the answer. The difficulty $x$ should only be checked at sword strengths.

Why? Suppose $x$ is between two adjacent sword strengths. Then the set of usable swords does not change, so $m(x)$ does not change, and the completed level count does not change. In that whole interval, increasing $x$ increases the score. So the best value in the interval is at the right endpoint, which is some sword strength.

So the plan is:

1. Sort the sword strengths.
2. Build prefix sums of $b$.
3. For each distinct sword strength $x$, compute how many swords have strength at least $x$.
4. Use binary search on prefix sums to find how many levels can be completed.
5. Maximize $x \cdot \text{levels}$.

If the sorted strengths are increasing, and we are at index $i$, then all swords from $i$ to $n-1$ have strength at least $a_i$, so

$m = n - i.$

For duplicate values, only the first occurrence matters, because it gives the largest usable count for that same difficulty. Later duplicate positions have the same $x$ but fewer counted swords if handled naively, which would only make the result worse. So skip repeated strengths after processing their first occurrence.

To compute completed levels, store prefix sums:

$p = [b_1, b_1+b_2, \dots, b_1+\dots+b_n].$

Then

$\text{levels} = \#\{p_i \le m\},$

which is exactly upper_bound(p.begin(), p.end(), m) - p.begin().

Edge cases:

• If even level $1$ needs more swords than available, completed levels can be $0$, giving score $0$.
• If all swords are huge and all $b_i=1$, the answer can be as large as $10^9 \cdot 2\cdot 10^5$, so use long long.
• $n=1$ works normally: either complete one level or zero.

Sorting costs $O(n \log n)$ per test case, and each distinct strength uses one binary search, so total complexity is

$O(n \log n)$

per test case. Across all test cases, this is fine because the total $n$ is at most $2\cdot 10^5$.