Can "codeforces 355C - Vasya and Robot" be solved with DP?

Initially I thought it has to be solved with DP. But the best function that I could think of is F(left, right, flag) which is obviously not feasible given n can be upto 1e5. Is the clever bruteforce mentioned in the editorial all we got or is there some other way to solve it with DP?