问题 1780 --ring沙盘游戏

1780: ring沙盘游戏★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 34  解决: 16
[提交][状态][命题人:]

题目描述

Ivy是如此地喜欢编程,以至于在面对游戏时也是如此。在沙盘游戏中有一个巨大的方形沙盘(长方形或者正方形),该沙盘被分隔成边长为1的小方格,每个小方格内有一个整数。沙盘玩家需要在沙盘中圈出一个方形(长方形或者正方形都可以)的区域(必须沿着小方格的边界划线,不能穿过小方格的内部),目标是争取被圈区域内的整数之和最大。

为了描述方便,Ivy把这个沙盘用n*m个整数来表示,每个整数所在位置表示沙盘中一个边长为1的小方格。

Ivy现在需要编程解决这样一个问题:在n*mnm列)个整数中选择一个x*yxy列)的方形区域(x最大可达ny最大可达m),使得这x*y个整数之和是所有可以选择的方形区域中最大的,并输出这个最大总和值。

输入

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

输出

一行一个整数,表示某个被圈出的方形区域中所有位置上整数之和,该值必须是所有可以圈出的方形区域所对应整数和中,总和最大的那个,该值确保不超过106
样例输入
Copy
3  3  
10 -21 9
7 8 4 
-6 1 0
样例输出
Copy
19

提示

【输入输出样例说明】圈出的方形区域是第二行的3个整数,即784,此三数之和为19,为所有可圈出区域中整数之和的最大值。             

【数据规模说明】

对于10%的数据,n,m<=5

对于40%的数据,n,m<=30

对于60%的数据,n,m<=40

对于90%的数据,n,m<=80

对于100%的数据,n,m<=280

来源

WXF 

[提交][状态]