#1369. 子矩阵的和

子矩阵的和

题目背景

前面接触了子串的概念,本题我们需要用到子矩阵的概念。类比着理解,子矩阵就是在原来的矩阵当中挖出一个部分,保证挖出的部分必须是规则的矩阵形状,你可以称这一部分为子矩阵。

例如原矩阵

1 2 3
4 5 6

其中

1 2
4 5

是它的子矩阵,但

1 3
4 6

不是

题目描述

给你一个 n×mn\times m 的矩阵 aa,每个位置的值为 ai,ja_{i,j},现在你要从整个矩阵中选择一个 s×ts\times t 的子矩阵,请你求出最大的子矩阵的和。

输入格式

第一行输入两个空格隔开的整数 n,mn,m

接下来 nn 行每行 mm 个空格隔开的数字。

最后输入两个空格空格隔开的整数 s,ts,t

输出格式

输出最大的 s×ts\times t 的和。

3 4
1 2 3 4
5 6 7 8
9 10 11 12
1 2
23

提示

样例一解释

3×43\times 4 的矩阵中,我们需要选择一个 1×21\times 2 的子矩阵,且和最大,很明显选择右下角 11,1211,12 这个位置构成的子矩阵,它的和为 11+12=2311+12=23

对于所有的数据范围满足 1n,m1021\leq n,m\leq 10^21sn,1tm1\leq s\leq n,1\leq t\leq m103ai,j103-10^3\leq a_{i,j}\leq 10^3