← 返回题目列表

AtCoder · awc0097_d

D. 最大矩形子数组和

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

分数: 400 分

问题陈述

高桥有一个网格 N 行和 M 列。所在行的单元格 i 和专栏 网格的 j 包含一个整数 A_{i,j}.

Takahashi 将从该网格中选择一个矩形区域,并计算该区域中包含的所有单元格的值的总和。这里,“矩形区域”是指由行之间的所有单元格组成的区域 r_1 和 r_2 (含)且其列位于 c_1 和 c_2 (含),其中 r_1, r_2 (1 \le r_1 \le r_2 \le N)和 c_1, c_2 (1 \le c_1 \le c_2 \le M) 是选定的整数。

Takahashi 希望选择矩形区域以使该总和最大化。请注意,矩形区域必须至少包含一个单元格,因此不可能选择没有矩形区域且总和为 0。特别是,即使所有单元格值为负,他仍然必须选择一些矩形区域。

找出高桥可以选择的矩形区域内的最大可能值之和。

约束

  • 1 \leq N \leq 500
  • 1 \leq M \leq 500
  • -10^4 \leq A_{i,j} \leq 10^4
  • 所有输入值均为整数

输入

N M
A_{1,1} A_{1,2} \ldots A_{1,M}
A_{2,1} A_{2,2} \ldots A_{2,M}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,M}
  • 第一行包含一个整数 N 表示行数和一个整数 M 表示网格的列数,以空格分隔。
  • 以下 N 行每条描述网格的一行。的 i- 这些行(1 \le i \le N) 包含值 行中单元格的 A_{i,1}, A_{i,2}, \ldots, A_{i,M} 网格的 i ,用空格分隔。

输出

在高桥可以选择的矩形区域内打印最大可能的值之和,作为单行的整数。


样本输入 1

3 3
1 -2 3
-4 5 6
7 -8 9

示例输出 1

18

示例输入 2

2 2
-5 -3
-1 -7

示例输出 2

-1

示例输入 3

5 4
2 1 -3 4
-1 3 2 -1
4 -2 1 3
-3 1 -4 2
1 2 3 -1

示例输出 3

14

示例输入 4

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

示例输出 4

77

示例输入 5

1 1
-7

示例输出 5

-7