Neo
레이팅 미적용의견: 0
\(6^{th}\) round, February \(7^{th}\) 2015
Let us denote \(A\)i,j as the element from matrix \(A\) located in the \(i\)^{th} row and \(j\)^{th} column. We say that
the matrix \(A\) is cool if this holds:
• r, \(s > 1\)
• \(A_{1}\){,} + \(A_{r,s}\) ⩽\(A_{1}\){,s} + \(A_{r,}\)
where \(r\) denotes the number of rows, and \(s\) the number of columns of matrix \(A\).
Additionally, we say that a matrix is extremely cool if each of its submatrices with at least two rows
and two columns is cool.
It is your task to determine the largest number of elements that are contained in an extremely cool
submatrix of the given matrix.
In test cases worth 60% of total points, it will additionally hold R, S ⩽350.
The first line of input contains two integers \(R\), \(S\) (2 ⩽R, S ⩽1 000) which represent the dimensions
of the matrix.
Each of the following \(R\) lines contains \(S\) integers that represent the elements in the matrix.
The
elements in the matrix will be integers from the interval [−\(10^{6}\), \(10^{6}\)].
The first and only line of output must contain the maximal number of elements that are contained
in an extremely cool submatrix of the matrix from the input. If an extremely cool submatrix doesn’t
exist, output 0.
3 3
1 4 10
5 2 6
11 1 3
3 3
1 3 1
2 1 2
1 1 1
5 6
1 1 4 0 3 3
4 4 9 7 11 13
-3 -1 4 2 8 11
1 5 9 5 9 10
4 8 10 5 8 8output
output
9
4
15Clarification of the third example: The solution is a matrix with an upper left corner in (3,2) and lower
right corner in (5,6).
평가 및 의견
Neo
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Neo