시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)224654634.848%

문제

You are given an $N \times M$ matrix $A$. Find the maximum sum of any subrectangular submatrix of this matrix.

Here, a subrectangular submatrix is defined as a contiguous submatrix formed by selecting any rectangular section of the given matrix $A$, such that the submatrix includes all rows and columns between two specified pairs of indices $(r_1, c_1)$ and $(r_2, c_2)$, where $1 \le r_1 \le r_2 \le N$ and $1 \le c_1 \le c_2 \le M$, plus the case when the submatrix is empty.

입력

The first line of input contains two space-separated integers: $N$ and $M$, denoting the size of the matrix. ($1 \le N \le M \le 100\,000;$ $1 \le NM \le 100\,000$)

The next $N$ lines of input contain $NM$ integers, where each line has $M$ space-separated integers, denoting the value of the matrix. Here, the $j$-th integer of the $i$-th line denotes $A_{ij}$. ($-10\,000 \le A_{ij} \le 10\,000$)

출력

Output the maximum sum of any subrectangular submatrix on a single line.

서브태스크 1 (3점)

Modified constraints apply: $1 \le N \le M \le 8;$ $1 \le NM \le 64$.

서브태스크 2 (13점)

Modified constraints apply: $1 \le N \le M \le 40;$ $1 \le NM \le 1\,600$.

서브태스크 3 (13점)

Modified constraints apply: $\underline{\boldsymbol{1 = N}} \le M \le 100\,000;$ $1 \le NM \le 100\,000$.

서브태스크 4 (71점)

Original constraints apply: $1 \le N \le M \le 100\,000;$ $1 \le NM \le 100\,000$.

예제 입력 1

4 5
1 2 -1 -4 -20
-8 -3 4 2 1
3 8 10 1 3
-4 -1 1 7 -6

예제 출력 1

29

The maximum submatrix is: $$\begin{bmatrix}-3 & 4 & 2 \\ 8 & 10 & 1 \\ -1 & 1 & 7\end{bmatrix}.$$

The sum of this submatrix is $-3 + 4 + 2 + 8 + 10 + 1 - 1 + 1 + 7 = 29$.

노트

(For Sogang students:) Note that this problem is an improvised version that matches the format of a problem in a general programming contest. While in the exam, the original scoring was:

  • $35$ points for Subtask 1.
  • $25$ points for Subtask 2.
  • $35$ points for Subtask 3.
  • $5$ points for Subtask 4.

채점 및 기타 정보

  • 예제는 채점하지 않는다.