题库/G4019

#G4019. [GESP202509 四级] 排兵布阵

    传统题 难度: 进阶 标签>GESPGESP四级二维枚举前缀和最大矩形
时间限制1000 ms
内存限制512 MiB
通过率100%1 / 1 次提交
题目描述 查看题解 开始编程Alt+E

G4019 · [GESP202509 四级] 排兵布阵

退出在线编程模式
进阶 读懂题意,让每一次思考成为成长。
时间限制1000 ms
内存限制512 MiB
通过率100%1 / 1 次提交

对应的选择、判断题:https://ti.luogu.com.cn/problemset/1192

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

输入格式

第一行,两个正整数 n,mn, m,分别表示地图网格的行数与列数。

接下来 nn 行,每行 mm 个整数 ai,1,ai,2,…,ai,ma_{i,1}, a_{i,2}, \ldots, a_{i,m},表示各行中的网格是否适合排兵。

输出格式

一行,一个整数,表示适合排兵的矩形区域包含的最大网格数。

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

说明与数据范围

对于所有测试点,保证 1≤n,m≤121 \leq n, m \leq 12,0≤ai,j≤10 \leq a_{i,j} \leq 1。

来源与评测数据

GESP C++ 4级,2025年09月第1题。

本题含12个自行生成的测试点,非官方原版测试数据;每题总分100分。

题目信息

#715
100%

1 次通过 · 1 次提交

练习难度 进阶
时间限制
1000ms
内存限制
512MiB

题目标签

暂无标签
上传者