#P3908. 区间最大
区间最大
Description
给出一个n行m列的二维网格a[1...n][1...m],从上往下,行的编号从1至n,从左往右,列的编号是1至m,第i行第j列的数是a[i][j]。有一个高度是r,宽度是s的长方形计算器。
每次你可以选择二维网格的某个格子(i,j)作为左上角,然后把计算器的左上角对准格子(i,j),覆盖下去,
计算器会自动计算出二维网格被覆盖区域的最大值,注意计算器的边要与二维网格的边平行,同时计算器不能超出二维网格。
二维网格被计算器覆盖的部分,称为二维网格的“子网格”。
现在的任务是:把计算器从二维网格的第1行第1列开始,从上往下,从左往右,每覆盖一次,就输出对应的“子网格”的最大值。
Input Format
第一行,n和m, 1<=n,m<=4000。
接下来是n行m列的二维网格,其中-10000<=a[i][j]<=10000。
最后一行是r和s。1<=r<=n, 1<=s<=m。
Output Format
共n-r+1行,每行输出m-s+1个数。
其中第i行第j列的数表示把计算器左上角对准二维网格第i行第j列格子,覆盖下去,计算器得到的最大值。
3 3
1 1 2
2 3 4
4 3 2
2 12 3 4
4 3 4