OJ Board

well I've solved this using dp ... simple recursive formula ...
btw thanks to mf for suggesting BS solution

Well probably there's a DP solution, but it's easier and faster to solve it with binary search.
Read misof's excellent analysis of a similar problem ("Turnpike" in that link)

I think Input provided by SADIQ(AIUB) in udebug is not in correct form . Please remove that kind of incorrect input.
take a look carefully .. The last 3 inputs are incorrect .

Test cases are too weak i think ... My AC code produces output 0 for

1

A 42

This case

Those who are getting wa are running dijkstra from target to destination but running this from u -> v but the graph should be v -> u so please reverse the input graph then run your dijkstra

#to_deepak
here 0,0 grid is marked as even . so if u get no answer (odd = 0 && even =0 ) then still your answer would be 1 0 .

just used straight forward DP . And got AC on 1st go.. with in .032 sec.

got ac on 1st submission actually 2D array is enough . as 'm' is not changing so we don't need 'm' as dp state

i just followed joe smith's suggestion and got ac nice explanation

O(n^2) solution will get TLE so must use O(nlogk) solution.

i used O(n^4) got ac . U must prune the search space . nothing else .