No problem now

The contest hasn't finished, I suppose.

does E need backtracking ?

Making a 2d dp would solve the problem. It's just like the standard minchange problem.

Let's say the monster current health is H. You can try any of the nth spell( can cast multiple times), the magic points increased would be B[i] and the remaining health would be H-A[i]. Overall complexity would be O(H*N) .

You can use dp[health] as minimum spells required to decrease health to 0.

Now as health has max limit of 10^4 and N spells as 10^3. You can iterate over each health from 0 to H and update your answer for dp[health].

i.e the recurrence is :

dp[health] = Summation_of_i_from_(0 to n)min(dp[health — a[i]) + b[i], dp[health]).

i.e you check by including all spells and get the best one.

Then, the answer is just dp[H].

Submission

If you're using python, O(H*N) (10^7) might be too much. Especially if you use a top-down memoized solution.

Turns out you can prune some of recursive calls if you sort the spells by highest attack per mana cost and break early when the min stops decreasing.

I can't prove that this is correct but it AC'd during the contest. Is it actually correct and if so can someone provide a proof?

Python code: https://pastebin.com/rTLWJXba

You give others a link of "my submissions" and will turn to our own submissions!

When you are too excited to post editorials #me

This would be the link to all your submissions: https://atcoder.jp/contests/abc153/submissions?f.User=Gary

Your submission link will direct everyone's personal submission. Can you provide the link differently?

can you tell me what is wrong in my solution. https://atcoder.jp/contests/abc153/submissions/9768886

can you elaborate on how to implement the binary search part

F can be solved in O(N) solution

H = 10^4 N = 10^3 not 10^4 so O(10^7).

U can use a single dp state. let dp[i] be the minimum cost required to make i tend to zero. so ur answer is dp[h].

Now let there be an intermediate state j and i be the presesnt start then

dp[i] = min(dp[i],dp[j]) + cost_required_to_reach_i_from_h.

https://atcoder.jp/contests/abc153/submissions/9765139

u can refer to my solution it's easy to understand

line 38 and 41 use 'd' instead of 'a'

You have $$$O(NH)$$$ states. For each state you do $$$O(H)$$$ calculations, so the overall complexity is $$$O(NH^2)$$$, which is not feasible for the given constraints.

You can calculate the answer for each state in $$$O(1)$$$, so the overall complexity will be $$$O(NH)$$$. Replace the while loop with:

dp[i][h] = min(solve(h, i + 1, n), solve(h - a[i], i, n) + b[i]);

solve(h, i + 1, n) indicates that we decide not to use spell i.
solve(h - a[i], i, n) + b[i] indicates that we use spell i. Note, that we don't advance to the next spell yet, because we may want to use spell i several times, and this allows us to avoid using the while loop.

Sidenote: It is actually possible to "squeeze" your solution. Notice, that if all a[i] were different, the total complexity would improve from $$$O(NH^2)$$$ to $$$O(H^2\log H)$$$, by the Harmonic series argument (see this or this). And for this problem it is possible to make all a[i] different, because for each unique a[i] we are only interested in the smallest cost b[i]. See this submission, which barely fits in the 2s TL with a couple of optimizations.

Edit: I just realized that the complexity of the second solution is probably $$$O(H^2\log H)$$$ rather than $$$O(NH\ log H)$$$.

In your binary search you don't seem to be using mid variable. Maybe the check's supposed to be m[mid].x <= atkrange?