#NH4739. NH.2023.初中.05.子网格

NH.2023.初中.05.子网格

题目描述

给出一个 nnmm 列的二维网格 a[1...n][1...m]a[1...n][1...m],从上往下,行的编号从 11nn,从左往右,列的编号是 11mm ,第 ii 行第 jj 列的数是 a[i][j]a[i][j]

有一个高度是 rr,宽度是 ss 的长方形计算器。

每次你可以选择二维网格的某个格子(i,ji,j)作为左上角,然后把计算器的左上角对准格子(i,ji,j),覆盖下去,计算器会自动计算出二维网格被覆盖区域的最大值,注意计算器的边要与二维网格的边平行,同时计算器不能超出二维网格。

二维网格被计算器覆盖的部分,称为二维网格的“子网格”。

现在的任务是:把计算器从二维网格的第 11 行第 11 列开始,从上往下,从左往右,每覆盖一次,就输出对应的“子网格”的最大值。

输入格式

第一行,nnmm1n,m40001 \le n,m \le 4000

接下来是 nnmm 列的二维网格,其中 10000a[i][j]10000-10000 \le a[i][j] \le 10000

最后一行是 rrss ( 1rn1 \le r \le n, 1sm1 \le s \le m )。

序号 满足性质 分值占比
1 n,m<=40 12%
2 n,m<=40 16%
3 n,m<=1000 26%
4 无特殊性质 46%

输出格式

nr+1n-r+1 行,每行输出 ms+1m-s+1 个数。

其中第 ii 行第 jj 列的数表示把计算器左上角对准二维网格第i行第j列格子,覆盖下去,计算器得到的最大值。

样例

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

样例解释

第 2 个样例,计算器的覆盖过程如下,其中红色的数是最大值。

img