Обсуждение @ 1146. Maximum Sum @ Timus Online Judge

it4.kp Trivial O(N^4) algorithm easily passes system tests [3] // Задача 1146. Maximum Sum 7 окт 2006 03:35

In 0.140 sec.

Yitao Re: Trivial O(N^4) algorithm easily passes system tests [2] // Задача 1146. Maximum Sum 16 июн 2007 16:57

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

Vedernikoff Sergey Re: Trivial O(N^4) algorithm easily passes system tests [1] // Задача 1146. Maximum Sum 22 июн 2007 14:00

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

S.77 Re: Trivial O(N^4) algorithm easily passes system tests // Задача 1146. Maximum Sum 6 авг 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).

Обсуждение задачи 1146. Maximum Sum