I got AC with O(n^3) solution, based on DP.
I suppose, that testcases are too weak. Anyway, I think, that it's not normal to get AC for O(n^3) solution.
)

My solution is n3, but it doesn't have to check all posibilities. Some part of array f[][] is never used. Besides, I don't know a better way.

It is not O(n^3): the expected number of tests for each sub-interval is 2 and thus DP is O(n^2).