Using Dijkstra with adjacency between each cell and the four next to its corners. Note that the cost does not increase when you make 2 moves using the same position change, e.g., up right. So the last position change needs to be maintained as well in the set / priority queue.

EDIT: 01-BFS works as well because edge weights can be only $$$0$$$ or $$$1$$$. So, instead of always pushing to the queue tail as we do in the normal BFS, when encountering an edge with weight $$$0$$$ we can push it to the queue front. This guarantees that costs are processed in non-decreasing order.

https://codeforces.net/problemset/problem/877/D similar problem.

You can use normal BFS too (not just 01-BFS).

Keep a 'seen' dictionary/map (seen[pos] = c where c is the min cost of getting to pos from (ax,ay) (the cost of the first time you get there since it's BFS)). Then for each pos loop on each diagonal adding (x,y,c+1) to the queue/deque (and to 'seen') until you reach a pos either outside the board or with a pawn OR in 'seen' with seen[pos]<c+1 (in order words you can reach that pos earlier from somewhere else so on the next move you'll have access to the rest of the diag).

I haven't proven the complexity but it passed.

Hi! You seem to terminate your loop when m == 0, but doing so you won't add a[i] (when you have 0 coupon left, you still need to pay for the item :) ) to your sum value.

Note that the largest number whose cube $$$\le 10^{18}$$$ is $$$10^{6}$$$. We can iterate on all the $$$10^{6}$$$ values, assume the current value is $$$a$$$, then use binary search to get the lowest $$$b$$$ giving answer $$$\ge$$$ $$$n$$$.

I use this method as well, and get WA, but don't know why.

The main idea is that we stop as soon as we meet a block or a cell which has beem visited or it is outside of board.

Still have no idea why this is not correct. Can anybody tell why and provide some counter example?

same approach. came here to post the same comment to get an answer. Can someone please answer?

18o3 SummerSky nagaraj41 Try this testcase.

4
2 4
1 1
.#..
#.#.
....
.#.#

2

3

BFS is not correct because moving one cell sometimes will increase the cost by 1 (when position change has changed, e.g., up right then up left) and sometimes will not increase the cost (when position change has not changed, e.g., up right then up right).

So, it may happen that for the same cell it has been put in the queue earlier using the cost change 1 and then we encounter it again but with cost change 0, where it should be put and processed before the earlier one.

EDIT: 01-BFS works as well because edge weights can be only $$$0$$$ or $$$1$$$. So, instead of always pushing to the queue tail as we do in the normal BFS, when encountering an edge with weight $$$0$$$ we can push it to the queue front. This guarantees that costs are processed in non-decreasing order.

Same way passed in the contest. I added the editoral, click here.

I solved it the same way as editorial but don't really understand why it works... I was just using intuition