#P9905. [COCI 2023/2024 #1] AN2DL

[COCI 2023/2024 #1] AN2DL

Description

当在 21 号楼下转悠的时候,你遇到了一面完全被数字覆盖的墙,这些数字被排成一个 nnmm 列的表格。然后你发现了有一个可以框柱 rrss 列的框靠在墙边,并且在框的旁边你发现了一支铅笔和一张纸,纸上有一个空白的表格。

你因为纸上的表格是空的而感到难过,所以你决定使用这个框来填充这个表格。

你把框靠在墙上,使第 ii 行第 jj 列的数字位于左上角,相框的边框与墙的边缘平行。考虑到相框内的数字,而且你喜欢大数,你决定把其中最大的数写在纸上表格的第 ii 行第 jj 列。

你对框在墙壁上的每一个可能位置(使框完全位于墙壁上,且框内正好有 r×sr \times s 个数字)重复上述过程,并确保相框边缘与墙壁边缘平行。

在你结束之后,纸上的表格甚至比墙壁还要漂亮。在纸上的表格中的数字是什么呢?

Input Format

第一行包含两个整数 nnm (1n,m4 000)m\ (1\le n,m\le 4\ 000),表示墙上表格的行数和列数。

接下来 nn 行,每行 mm 个整数 ai,j (ai,j10 000)a_{i,j}\ (|a_{i,j}|\le 10\ 000),其中 ai,ja_{i,j} 表示墙上表格第 ii 行第 jj 列的数。

最后一行两个整数 rrs (1rn,1sm)s\ (1\le r\le n,1\le s\le m),表示框的大小。

Output Format

输出纸上表格中的所有数字。

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

Hint

【样例解释#1】

只有一个 3×33\times 3 的子矩阵,且是整个矩阵,它的元素最大值是 44

【样例解释#2】

矩阵和它的每个 2×12\times 1 的子矩阵如下图所示,其中标红的数为最大值:

【数据范围】

对于 100%100\% 的数据,1n,m40001\leq n,m\leq 4000Ai,j10000\lvert A_{i,j}\rvert\leq 100001rn1\leq r\leq n1sm1\leq s\leq m

本题采用捆绑测试。

子任务 特殊性质 分值
11 n,m40n,m\leq 40r=nr=ns=ms=m 1212
22 n,m40n,m\leq 40 1717
33 n,m1000n,m\leq 1000 2525
44 无特殊性质 5656

【说明】

本题分值按 COCI 原题设置,满分 110110

题目译自 COCI2023-2024 CONTEST #1 T3 AN2DL