Discussion @ 1146. Maximum Sum @ Timus Online Judge

I've AC in O^4,but I wonder if there is a O^3 way

Posted by bbs.hasea.com 12 Sep 2007 19:01

code deleted

Edited by author 13.09.2007 17:11

Re: I've AC in O^4,but I wonder if there is a O^3 way

Posted by awpris 12 Sep 2007 20:37

Your Solution C++: time = 0.187
Solutin in Pascal (other algorithm): time = 0.031
Pleace, delete your solution code :)

Re: I've AC in O^4,but I wonder if there is a O^3 way

Posted by bbs.hasea.com 13 Sep 2007 17:12

code deleted

Re: I've AC in O^4,but I wonder if there is a O^3 way

Posted by Kiril Kafadarov 7 Jul 2008 16:11

There is an O(n^3) way(my solution is that). First you must save the sum of the elements form the first to each of the others in every row. Then for each column I and each column J
(J>=I) you sum all the rows (using the first step). On each step you check if the sum now is better than the max.If the sum gets below zero you make it zero and continue.

Kiril Kafadarov 1146 C++ Accepted 0.015 197 KB

Re: I've AC in O^4,but I wonder if there is a O^3 way

Posted by stalkerore 19 May 2013 18:58

дай пожалуйста код)

Discussion of Problem 1146. Maximum Sum