#4038. [GESP2509 四级] 排兵布阵

[GESP2509 四级] 排兵布阵

排兵布阵

题目描述

作为将军,你⾃然需要合理地排兵布阵。地图可以视为 ⾏ 列的⽹格,适合排兵的⽹格以 1 标注,不适合排兵 的⽹格以 0 标注。现在你需要在地图上选择⼀个矩形区域排兵,这个矩形区域内不能包含不适合排兵的⽹格。请问 可选择的矩形区域最多能包含多少⽹格?

输入格式

第⼀⾏,两个正整数 ,分别表⽰地图⽹格的⾏数与列数。 接下来 ⾏,每⾏ 个整数 ,表⽰各⾏中的⽹格是否适合排兵。

输出格式

⼀⾏,⼀个整数,表⽰适合排兵的矩形区域包含的最⼤⽹格数。

样例输入 #1

4 3
0 1 1
1 0 1
0 1 1
1 1 1

样例输出 #1

4

样例输入 #2

3 5
1 0 1 0 1
0 1 0 1 0
0 1 1 1 0

样例输出 #2

3

数据范围

对于所有测试点,保证 , 。

知识点与难度

本题涉及的知识点从属于 GESP 4级,难度等级:⭐⭐⭐ 。


测试点分布

Subtask 分值 测试点编号 说明
0 10 1~2 样例
1 20 3~8 小规模 / 特殊性质
2 15 9~11 Hack
3 30 12~20 中大规模
4 25 21~25 随机回归

生测试数据后,按实际 subtask 分组改写上表。