Discussion @ 1146. Maximum Sum @ Timus Online Judge

Trivial O(N^4) algorithm easily passes system tests

Posted by it4.kp 7 Oct 2006 03:35

In 0.140 sec.

Re: Trivial O(N^4) algorithm easily passes system tests

Posted by Yitao 16 Jun 2007 16:57

My algo is O(N^4) too,AC in 0.046sec...

Re: Trivial O(N^4) algorithm easily passes system tests

Posted by Vedernikoff Sergey 22 Jun 2007 14:00

Do you know a method how to solve it faster???

Re: Trivial O(N^4) algorithm easily passes system tests

Posted by S.77 6 Aug 2011 21:25

My algo is O(N^3). I just read the input matrix row by row and store the maximal sum of subrectangle for each bottom side projection using DP. I did it with 0.015 secs (never did faster).

Discussion of Problem 1146. Maximum Sum