← 返回题目列表

AtCoder · dwango2016qual_d

D. 花园

中文机器翻译题面 查看原题

問題文

dwango 公司拥有一个宽广的庭院。这个庭院南北方向有H行、东西方向有W列,每个区画的尺寸为1米方形。 从北边算起第i行、从西边算起第j列的区画称为区画(i,j)。 庭院里开满了各种花,每个区画都有一个整数表示该区画花的观赏价值。设区画(i,j)的花的观赏价值为 B_{i,j}。

决定至少由一个区块组成的两个矩形,用栅栏将这两个矩形围起来,将未被围起的地方作为道路,从而让庭院变得整洁。这里,两个矩形中包含相同区块是不允许的,但栅栏重叠没有问题。

庭院整体的整洁度,是由任意一个矩形围起来的区块的美观度总和。

为了打造理想的庭园,首先需要求出整洁度的最大值。 请编写一个程序来求庭院整体整洁度的最大值。


入出力

输入是按以下格式从标准输入给出的。

H W
B_{1,1} B_{1,2} … B_{1,W}
:
B_{H,1} B_{H,2} … B_{H,W}
  • 1 每行分别表示庭园南北、东西方向的长度。 H, W (2 ≦ H ≦ 300, 2 ≦ W ≦ 300) 用空格分隔。
  • 1+i (1 ≦ i ≦ H)每行从北向i第n个区块的美观度表示W个整数 B_{i,1}, ...,B_{i,W} 用空格分隔。
  • -10^9≦B_{i,j}≦10^9 (1 ≦ i ≦ H, 1 ≦ j ≦ W) 成立。

配点

针对此问题设置了部分分数。 如果正确答案是满足

  • H ≦ 50, W ≦ 50 的数据集 如果正确答案是满足 50 点。
  • 如果所有测试用例都正确,则除了上述之外50点。

出力

当确定两个矩形时,庭院整体整洁度的最大值1请按行输出。输出的补充内容也请换行。


入力例1

3 3
1 1 1
1 1 1
1 1 1

出力例1

9

2用几个长方形覆盖整个庭院时,整洁度达到最大9。


入力例2

3 3
-1 -1 -1
-1 -1 -1
-1 -1 -1

出力例2

-2

但有时整洁度残值也可能为负。请注意,长方形必须至少包含一个小区。


入力例3

2 3
5 -1 8
-1 4 -1

出力例3

16

例如,可以像下面这样围起来。

../../assets/statements/atcoder/dwango2016qual_d/001-d2b1d01f05fb24008e4e27d1.webp

入力例4

4 4
5 2 -3 2
3 8 -3 -10
4 5 3 2
-5 -3 3 5

出力例4

40