#arc0252. [arc025_2]チョコレート
[arc025_2]チョコレート
问题描述
有一个 行 列的巧克力。每个方格可以是黑巧克力或白巧克力。黑巧克力和白巧克力不共享边界(也就是说,巧克力呈棋盘格纹样)。每个方格中的巧克力浓度是确定的。以下是巧克力的示例(数字表示浓度)。
妹妹从这块巧克力中切出一个矩形区域来溶化,制作巧克力奶油。妹妹对巧克力的味道十分讲究,她希望使用的黑巧克力和白巧克力的浓度之和相等(如果某种颜色的巧克力没有被使用,则将其浓度视为0)。
妹妹想知道满足条件的切割方式中,使用的巧克力方格的最大数目是多少。
输入
输入以以下格式从标准输入读取:
·· ·· : ··
- 第 1 行包含巧克力的行数 和列数 ,用空格分隔。
- 第 2 至 行包含浓度信息。每行包含 个非负整数,用空格分隔。第 行第 个整数 表示以左上角为基准,第 行第 列方格的浓度。
输出
如果存在满足条件的切割方式,则输出其中使用的方格数的最大值;如果不存在,则输出 0
。输出末尾包含换行符。
输入示例1
3 4
4 6 2 5
3 5 6 7
2 5 5 6
输出示例1
6
如下图所示,切割一个 行 列的矩形区域,可以使方格数为 ,且浓度之和为 。
输入示例2
2 2
4 0
7 3
输出示例2
4
注意其中包含浓度为 的情况。
输入示例3
2 3
0 0 0
1 2 3
输出示例3
3
输入示例4
3 3
1 2 3
6 5 4
7 8 9
输出示例4
0
在这个例子中,不存在满足条件的切割方式。
输入示例5
1 5
0 1 2 3 4
输出示例5
1
请注意,即使只切割黑巧克力或白巧克力,也可能存在满足条件的情况。