1486. 月饼盒

时间限制 1000 ms   内存限制 128 MB

一个被分为  n*m 个格子的月饼盒,第  i  行第  j  列位置的格子里面有  a  [  i  ,  j  ]个月饼。本来CCC老师打算送这盒月饼给某人的,但是就在要送出月饼盒的前一天晚上,一只极其可恶的老鼠夜袭月饼盒,有部分格子被洗劫并且穿了洞。CCC老师必须尽快从这个月饼盒里面切割出一个矩形月饼盒,新的月饼盒不能有洞,并且CCC老师希望保留在新月饼盒内的月饼的总数尽量多。任 务 :请帮CCC老师设计一个程序  计算一下新月饼盒最多能够保留多少月饼。

输入数据

第一行有两个整数&nbsp n、m。第&nbsp i&nbsp +&nbsp 1&nbsp 行的第&nbsp j&nbsp 个数表示&nbsp a&nbsp [&nbsp i&nbsp ,&nbsp j&nbsp ],如果这个数为&nbsp 0&nbsp ,则表示这个位置的格子被洗劫过。其中:1&nbsp ≤&nbsp n,m&nbsp ≤&nbsp 300&nbsp ,&nbsp 0&nbsp ≤&nbsp a&nbsp [&nbsp i&nbsp ,&nbsp j&nbsp ]≤&nbsp 255

输出数据

输出最大月饼数。

样例输入

复制
3 4
1 2 3 4
5 0 6 3
10 3 4 0
 · \n
 · · · \n
 · · · \n
  · · · \n

样例输出

复制
17
  \n

样例说明

10&nbsp &nbsp 3&nbsp &nbsp 4

这个矩形的糖果数最大

提交

请先 登录

Source

From  OIBH. dfh改编!

© 2024 FAQs Contact About