ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1146. Maximum Sum

How my O(n^4) solution got AC.
Posted by Raman Gupta 17 Dec 2012 00:44
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.
Posted by Andrew Sboev [USU] 17 Dec 2012 22:41
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)) =))