my O(n^3) dp got accepted in 0.89sec, though i used an O(n^2) algorithm later and ran much faster.

Of course, it works. Moreover, my O(n^3) dp works in 0.48sec. And I'm sure, that it isn't limit. Obvious, that it's impossible to break O(n^3) solutions with current constraint for n.