Got it! Solved F and ranked 296!^^

666

did your sample test case pass in local? Same problem with me. My sample testcase pass in local but failing on submission

It's a dogshit problem. Just write bruteforce with pragmas (that O3 optimization) and it will magically work.

Idk if there's a 'real' smart solution, but this is intended as far as I can see from evima's editorial lmao.

I did Bfs

It's just a trivial bfs where you update the maximum remaining steps you can take from point (x,y). It works in O(H*W*N) because you'll update each point (x,y) at most N times.

I got a simple solution using priority queue, my ideia is use the hightest energy first and reset visited checking ttable every time use a medicine. https://atcoder.jp/contests/abc348/submissions/52162753

You can check my video editorials for D and E

You can solve it by BFS. This is my code.

Maybe you can reference my code, $$$f_{i, j}$$$ means maximum from point $$$S$$$ to $$$(i, j)$$$，finally we can check if the point $$$f_{T} \ge 0$$$ and we can see the answer.

code

Agree. I even thought half an hour. qwq

use map.look it. https://atcoder.jp/contests/abc348/submissions/52071264

set ANS to 2*1e18, it works for me.

Just do the Brute Force way. Time complexity will be around O(NWH).

Sort the items in order of increasing $$$b_i$$$. For two different values of $$$k$$$, say $$$x$$$ and $$$y$$$, let in the optimal choice of elements, the max values of $$$b_i$$$ are $$$b_x$$$ and $$$b_y$$$ respectively. We can prove that if $$$x < y$$$ then $$$b_x \leq b_y$$$.

Also, if you fix some $$$b_i$$$, then the optimal answer for some $$$k$$$ is just the sum of maximum $$$k$$$ $$$a_i$$$$$$s$$$ in the prefix ending at $$$i$$$ minus $$$b_i$$$. So, for a fixed $$$b_i$$$ and $$$k$$$, you can evaluate the answer in $$$O(logn)$$$ using some data structure that gives the sum of $$$k$$$ maximum elements in a range.

To evaluate for each $$$k$$$, you can use the fact that the optimal $$$b_i$$$ values are monotonically non-decreasing. It is a common idea to use Divide and Conquer. Refer to this article for more info on this idea.