Hello everyboby! I found solution in O(n^4), what about others? (-)

But it is very slow! Is it possible to accelerate it without precalculation? (-)

Of course... (+)

The fastest solution is precalc (as usual :] ), but you can make your solution very fast without it. It is clear that there is some physical dependence in this problem - the line of optimal movement is some function (a parabola, I presume). So you can look for several nearest points with integer coordinates and use dp only for them. But it is much more difficult and unsafe, isn't it?

Re: Of course... (+)

Not parabola, but cycloid! It's variational stuff :)!

Re: Of course... (+)

What is cycloid's formula?