An2dl
레이팅 미적용의견: 0
While wandering around Building 21, you came across a wall completely covered
with numbers, arranged in a table of \(n\) rows and \(m\) columns. Soon you noticed
that there was a frame leaning against the wall large enough to frame \(r\) rows and
\(s\) columns of the table on the wall. And next to the frame you found a pencil and
a piece of paper containing an empty table.
You are sad that the table on the piece of paper is empty, so you decided to play
around with the frame to fill it.
You leaned the frame against the wall so that the number in the \(i-th\) row and \(j-th\) column is in the upper
left corner, and the borders of the frame are parallel to the edges of the wall. Considering the numbers
inside the frame, and since you like large numbers, you have decided to write the largest among them in
the \(i-th\) row and \(j-th\) column of the table on the piece of paper.
You repeated the process for every possible position of the frame on the wall (such that the frame is
entirely on the wall, and that there are exactly \(r \times s\) numbers inside it), making sure that the edges of the
frame are parallel to the edges of the wall.
When you were done, the table on the piece of paper was even more beautiful than the one on the wall.
What numbers are in the table on the piece of paper?
Subtask 1 (12 points): n, \(m \le 40\), \(r = n\), \(s = m\)
Subtask 2 (17 points): n, \(m \le 40\)
Subtask 3 (25 points): n, \(m \le 1\,000\)
Subtask 4 (56 points): No additional constraints.
The first line contains two integers \(n\) and \(m\) (\(1 \le n\), \(m \le 4\,000\)), the number of rows and columns of the
table on the wall.
Each of the following \(n\) lines contain \(m\) integers \(a\)i,j (|\(a\)i,j| ≤10 000), where \(a\)i,j is the number in the \(i-th\)
row and \(j-th\) column of the table on the wall.
The last line contains two integers \(r\) and \(s\) (\(1 \le r \le n\), \(1 \le s \le m\)), the size of the frame.
Output the numbers written in the table on the piece of paper.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 12점 | n, \(m \le 40\), \(r = n\), \(s = m\) |
2 | 17점 | n, \(m \le 40\) |
3 | 25점 | n, \(m \le 1\,000\) |
4 | 56점 | No additional constraints. |
3 3
1 1 2
2 3 4
4 3 2
3 343 3
1 1 2
2 3 4
4 3 2
2 12 3 4
4 3 45 5
-1 -3 -4 -2 4
-8 -7 -9 -10 11
5 2 -8 -2 1
13 -3 -2 -6 -9
11 6 2 7 4
2 3-1 -2 11
5 2 11
13 2 1
13 7 7Clarification of the first example:
The frame is big enough to fit the entire table on the wall. The largest number inside the frame is 4, so
that is the only number written on the table on the piece of paper.
Clarification of the second example:
All possible frame positions are shown in the picture below. The largest number for each of the positions
is written in red.
평가 및 의견
An2dl
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
An2dl