题目描述

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 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?

题目大意

给定 $n,m,r,s$ 和一个 $n\times m$ 的整数矩阵 $A$，求它每个 $r\times s$ 的子矩阵的元素最大值。

输入格式

第一行两个整数 $n,m$ 表示矩阵的高和宽。

接下来 $n$ 行每行 $m$ 个整数，表示矩阵 $A$。

最后一行两个整数 $r,s$。

输出格式

$n-r+1$ 行，每行 $m-s+1$ 个数，第 $i$ 行 $j$ 列的数表示以 $(i,j)$ 为左上角的 $r\times s$ 的子矩阵元素的最大值，即 $\max\limits_{i\leq x\leq i+r-1,j\leq y\leq j+s-1}A_{x,y}$。

题目大意

给定 $n,m,r,s$ 和一个 $n\times m$ 的整数矩阵 $A$，求它每个 $r\times s$ 的子矩阵的元素最大值。

3 3
1 1 2
2 3 4
4 3 2
3 3

4

3 3
1 1 2
2 3 4
4 3 2
2 1

2 3 4
4 3 4

5 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 7

提示

【样例解释#1】

只有一个 $3\times 3$ 的子矩阵，且是整个矩阵，它的元素最大值是 $4$。

【样例解释#2】

矩阵和它的每个 $2\times 1$ 的子矩阵如下图所示，其中标红的数为最大值：

【数据范围】

对于 $100\%$ 的数据，$1\leq n,m\leq 4000$，$\lvert A_{i,j}\rvert\leq 10000$，$1\leq r\leq n$，$1\leq s\leq m$。

本题采用捆绑测试。

子任务	特殊性质	分值
$1$	$n,m\leq 40$，$r=n$，$s=m$	$12$
$2$	$n,m\leq 40$	$17$
$3$	$n,m\leq 1000$	$25$
$4$	无特殊性质	$56$

【说明】

本题分值按 COCI 原题设置，满分 $110$。

题目译自 COCI2022-2023 CONTEST #1 T3 AN2DL。