logo AlgoBeat OnlineJudge
登录 注册

#101850. [BZOJ 1850] Submatrix

内存限制:64 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

很久很久很久以前,有一个古老的主题公园,有一个伟大的工程师 QDC,她打算在公园修建一个花坛,花坛周围修建一片绿化带。如果把公园看成一个 的矩形,也就是说把公园划分成了 块土地,那么绿化带和花坛可以看成一个 的矩形,花坛可以看成一个 的矩形。如图所示:

20 19 18 17 16
15 14 13 12 11
10  9  8  7  6
 5  4  3  2  1

QDC 经过一段时间的对土地的考察,给每一块土地定了一个「肥沃度」。绿化带的肥沃度定义为 块土地的肥沃度的总和,她希望修建这样的一片绿化带,使得绿化带的肥沃度最大。

花坛一定要完全在绿化带的包围之中,也就是说, 的矩阵边上的元素一定不在 的矩阵中。

当然,这种问题是难不倒 QDC 的,但是她还有别的更重要的工作要做,于是这个工作就交个你了,薪水很高的哦!

输入格式

第一行有六个正整数 。结下来 行,每行有 个正整数,第 行第 列的数表示 的肥沃度。

输出格式

一个正整数,表示绿化带的最大肥沃程度。

样例

样例

样例输入 #1

4 5 4 4 2 2
20 19 18 17 16
15 14 13 12 11
10 9 8 7 6
5 4 3 2 1

样例输出 #1

132

数据范围与提示

的数据,

的数据, 肥沃度