最大加权矩形
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
为了更好地备战 NOIP 2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为：我们不光需要机房，我们还需要运动。于是她们决定找校长申请一块电脑组的课余运动场地。听说她们都是电脑组的高手，校长没有马上答应他们，而是先给她们出了一道数学题，并告诉她们，她们能获得的运动场地的面积就是她们能找到的这个最大的数字。
校长给她们一个大小为 的矩阵，矩阵中的每一个元素都有一个整数权值，要她们求出该矩阵中的最大加权矩形（即从中找一大小不限的矩形，使其中包含的所有元素的权值和最大）中所有元素的权值和，且矩阵中每个元素的权值均在区间 内。
几个女孩子有点犯难了，于是就找到了电脑组精打细算的 HZH,TZY 小朋友帮忙计算，但是遗憾的是，他们的答案都不一样。涉及土地的事情我们可不能含糊，你能帮忙计算出校长所给的矩形中加权和最大的矩形吗？
输入格式
第一行包含一个正整数 。
接下来 行每行包含 个整数，表示给定的矩阵。
输出格式
输出一行一个整数，表示该矩阵的最大加权矩形中所有元素的权值和。
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
15
提示
样例解释
该矩阵中的最大加权矩形为
9 2
-4 1
-1 8
它们的和为 。
数据范围
对于 的数据，。
国庆集训入门组作业——前缀和&差分
- Status
- Done
- Problem
- 18
- Open Since
- 2025-10-3 9:00
- Deadline
- 2025-10-18 23:59
- Extension
- 24 hour(s)