Programming Challenge

[blacklee]

I implemented two solutions. The first one ran in O(N^4) time and it took 6 of the maximum 10 seconds. So I tried again and made one that runs O(N^3). This ran in a small fraction of a second so it should be safe from the notorious re-judging that seems to kill efficient but not completely correct solutions.

How does the re-judging work? Do they run it with a different input? I didn't know they do it.

[blacklee]

I think I deleted one of my messages, sorry.  :-)

My solution ran 0:021 seconds, and I think it is a completely correct solution, but I'm not 100% sure.

Your C++ program has solved Ok the problem 108 (Maximum Sum) in 0.021 seconds with low memory spent.

Thanks for the hints, the problem really is easier than it first appears.

[R. Andrew Lamonica]

How does the re-judging work? Do they run it with a different input? I didn't know they do it.

I am not sure exactly how re-judging works.  It seems a little hit-and-miss to me.  I have had programs that were correct get rejudged as wrong just to be rejudged as correct again a few days later without any action on my part.  

The one thing that I do know is that they keep a copy of each program you submit and then they re-run the judging every now and then.  

I suspect that this is to catch people who are sending the same result to different accounts and to find programs that were approved just because they ran on a fast processor and not because they were correct.

[blacklee]

So,if my solution is accepted, is it pretty safe to assume that it's completely correct? For example, do I need to test for maximum sum being only one cell; or the Judge tests with various input? I'm pretty sure the solution works, I'm just curious.

I'm also curious how other people get a better time. Is it because they have a more efficient algorithm? Is there a way to optimize my code without changing the algorithm?