After sorting we have the problem of
finding maximal-sum submatrix
but it has O(n^3).
After additional thinking- all OK!
This is the way.For eaach row range [i1,i2]
it should  mantain set of nonzero columns
and number of such colums in mean must be 1-10

Pardon...Tle. Instead 1-10 really we have 500

Edited by author 19.10.2009 20:45

Max-sum submatrix problem has O(N^2 log n) complexity
As I heard, it is enough for this problem

How? I only know how to solve Max-sum submatrix problem with O(n) non-zero elements with this asymptotic

(deleted)

Edited by author 29.10.2009 04:19

OK, I see my mistake now :o)
N is number of non-zero elements, not the side of the matrix :o)