ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1146. Maximum Sum

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
дай пожалуйста код)