1) bsearch the overspeeding (o)

2) assume that you overspeed with o through every edge, so your total speed is vi + o.

3) then use Dijkstra on time and see if you can get to n in no more than T.

A possible solution (I never tried to implement it, I'm too lazy):

• consider the squares in a single row; we pass those squares once from the left and once from the right, only counting distances from the bases in the columns we've passed already; the result for any square is the minimum of those 2 values for this square

• in every column, it's apparently enough to consider the bases in rows closest to our row, so for every square, the distance we're looking for is a minimum of some quadratic functions for given x-coordinate (the y-coordinate is the same in our row)

• now, observe that if we have quad. functions in forms

f(x)=x**2+Ax+B; g(x)=x**2+Cx+D

where f(x) > g(x), A > C, then for any larger x, we'll still have f(x) > g(x), so we can just forever forget the base corresponding to f(x) and never check if it gives the minimum - so, we need to keep a list of possible functions (bases) and be able to choose the one that gives a minimum and drop one all which can't give a minimum anymore (and add one, but that's trivial), and very fast. So we keep their linked list, sorted decreasingly in f(x) and increasingly in the linear coefficient (A), and in a heap, we keep "events": the minimal x for which a function with larger A obtains a larger value than the one right before it in the list; when we move to the next square in the row and add the (at most 2) nearest bases in that column, we keep deleting functions for which this happens and re-calculate those values in the heap (we still need to take care of situations in which the other function of the given event has been deleted already), and then choose the last function in the list. It's similar to slope optimization in dynamic programming.

• every function add/delete can be processed in log time (we only have O(C) functions and therefore also events); we do this for every row, so total time is O(RC log C).

From every base send 4 spies in four directions. Initial lenght width of the spy is 1, but with each step we add 1 dot on both sides. Spy tries to update the dots it meets, if he is the first to reach a dot. When a spy detects that it stumbled on the area closer to another spy (who visited the dot earlier) it reduces its line.

The idea is taken from stones thrown into water, but instead of circles there are squares.

In my implementation I was checking the spy line and if there was a gap of length at least 3, the line was split to skip that hole (spies are split as well, so their number grows in this case). In dense board many spies get quickly totally removed. Spies are kept in queue.

I was so curious whether this approach was acceptable. Now that timus released this problem, I know it works (got AC with 1.23 s, however needed to work hard on memory usage, using bit fields).