首页 > 代码库 > 霰弹枪[二维的前缀和]

霰弹枪[二维的前缀和]

 在clyz有一个很厉害的枪手叫做东哥,他的女神qy被本地一个著名的黑帮老大XXX给绑架了,东哥急切地想要找回qy,向椅子买了几件武器。因为首先要轰开clyz的大门,所以他选择了霰弹枪。clyz的大门由N*M块石头组成,而东哥的体积为R行C列(东哥不可被切开),他为了省子弹,他只能轰出一个恰好自己通过的洞,每块石头的价值不同,打碎可获得的金钱也不同,东哥要攒钱买武器,所以要选择轰最大价值的一部分石头,现在他想要知道自己能够获得多少金钱购买下一把武器。

输入格式

第1行:4个正整数N,M,R,C

第2..N+1行:每行M个正整数,第i+1行第j个数表示num[i][j]

输出格式

1行:1个整数,表示东哥最多能获得的金钱

输入样例

3 5 2 3

5 2 7 1 1

5 9 5 1 5

3 5 1 5 3

输出样例

33

数据范围

 

对于60%的数据:1 <= N,M <= 200

对于100%的数据:1 <= N,M <= 1,000

1 <= R <= N, 1 <= C <= M

1 <= num[i][j] <= 1000

保证结果不超过2,000,000,000

 

霰弹枪[二维的前缀和]