How my O(n^4) solution got AC.

I was little discouraged when my O(n^4) solution got AC.What remains the purpose of Dp ,if I could do it by complete search.

Please mail me the O(n^3),O(n^2),O(n) solution for this task,any or all complexity written here.

My mail id is royalbird.raman@gmail.com

thanks for your support

Re: How my O(n^4) solution got AC.

O(n) cannot be achieved in this problem, because of O(n^2) input.

Re: How my O(n^4) solution got AC.

Posted by

Lord_F 26 Dec 2012 21:31

I think you use a kind of DP when you sum the numbers in every rectangle.

(In fact, the most complete search has the complexity O(n^6)) =))