#1212. 沙盘游戏

沙盘游戏

题目描述:

在沙盘游戏中有一个巨大的方形沙盘(长方形或者正方形),该沙盘被分隔成边长为 1 的小方格,每个小方格内有一个整数。沙盘玩家需要在沙盘中圈出一个方形(长方形或者正方形都可以)的区域(必须沿着小方格的边界划线,不能穿过小方格的内部),目标是争取被圈区域内的整数之和最大。 为了描述方便,Ivy把这个沙盘用 n * m 个整数来表示,每个整数所在位置表示沙盘中一个边长为 1 的小方格。 lvy现在需要编程解决这样一个问题:在 n * m (n 行 m 列)个整数中选择一个 x * y ( x 行 y 列)的方形区域(x 最大可达 n,y 最大可达 m),使得这 x * y 个整数之和是所有可以选择的方形区域中最大的,并输出这个最大总和值。

输入格式:

第一行包含n,m,x,y四个整数,中间用一个空格分隔,分别表示原始方形区域中所包含的行数和列数。下面有n行,每行m个整数(每个整数的范围是-200到200)组成的数据。

输出格式:

一行一个整数,表示某个被圈出的方形区域中所有位置上整数之和,该值必须是所有可以圈出的方形区域所对应整数和中,总和最大的那个,该值确保不超过10^6。

输入样例:

3  3  1  3
10 -21 9
 7  8  4
-6  1  0

输出样例:

19

样例解释

数据范围约定

n,m <= 3000