#2152. [2013 安徽省]糖果盒(candybox)

    ID: 2152 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数组前缀和系列2013安徽省小学组

[2013 安徽省]糖果盒(candybox)

题目描述

卡卡西帮影院经理解决了难题,终于可以和妈妈安心的观看了电影。电影太精彩了,卡卡西在电影放映过程中,多次拍手叫好。放映结束后,卡卡西正准备和妈妈牵手回家,被影院经理拦住了。那位和蔼的叔叔满脸笑容的对卡卡西说:“小朋友,谢谢你之前帮我解决了难题,这可帮了我一个大忙啊!作为对你的感谢,我想赠送你这个糖果盒。这个糖果盒可不一般哦,只有足够聪慧,回答对问题并完成任务的小朋友,才能从中取出糖果”。

卡卡西痴迷的望着这个金光闪闪的糖果盒,瞪大的双眼里充满了好奇。这是一个被分为 NMN * M 个格子的飘着芳香的糖果盒,第 ii 行第 jj 列位置的格子里面有 a[i][j]a[i][j] 颗糖。但是经理告诉卡卡西,不幸的是,前一天晚上,一只极其可恶的老鼠夜袭糖果盒,有部分格子被洗劫并且穿了洞。为了让糖果盒保持美观,必须从这个糖果盒里面切割出一个新的不能有洞的矩形糖果盒,并且卡卡西希望保留在新糖果盒内的糖的总数尽量多,这样她就能吃到尽可能多的糖。

小朋友们,请你们帮卡卡西设计一个程序,计算一下新糖果盒里最多能够保留多少糖果,从而使卡卡西获得这个糖果礼盒。

输入格式

N+1N+1 行,第一行有两个正整数 NNM(1N300,1M300)M(1≤N≤300, 1≤M≤300)。后面 NN 行每行 MM 个正整数,第 i+1i+1 行的第 jj 个正整数 a[i][j](0a[i][j]255)a[i][j](0≤a[i][j]≤255),表示糖果盒的第 ii 行第 jj 个格子里的糖果个数,如果这个数为 00,则表示这个位置的格子被老鼠洗劫过,即该位置是个洞。

输出格式

输出一个正整数,即能得到的最大糖果数。

样例

输入#1

3 4
1 2 3 4
5 0 6 3
10 3 4 0

输出#1

17

解释#1

糖果盒为 343 * 4,糖果盒的第 22 行第 22 个格子和第 33 行第 44 个格子的糖果被老鼠吃了,现在是个洞,从中切割出一个包含尽可能多的糖果的不能有洞的矩形糖果盒为红色标注区域,糖果数为 1717

数据范围

40%的数据,1N101M101≤N≤10,1≤M≤10

60%的数据,1N1001M1001≤N≤100,1≤M≤100

100%的数据,1N3001M3001≤N≤300,1≤M≤300