| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 224 | 65 | 46 | 34.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.
Modified constraints apply: $1 \le N \le M \le 8;$ $1 \le NM \le 64$.
Modified constraints apply: $1 \le N \le M \le 40;$ $1 \le NM \le 1\,600$.
Modified constraints apply: $\underline{\boldsymbol{1 = N}} \le M \le 100\,000;$ $1 \le NM \le 100\,000$.
Original constraints apply: $1 \le N \le M \le 100\,000;$ $1 \le NM \le 100\,000$.
4 5 1 2 -1 -4 -20 -8 -3 4 2 1 3 8 10 1 3 -4 -1 1 7 -6
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:
University > 서강대학교 > CSE4152 문제해결프로그래밍실습 > 2024-2학기 중간고사 코딩 테스트 4번