QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 128 MB Total points: 100

#106. 炸弹

Statistics

地球人和外星人正在争夺火星。战斗发生在一个大小为 $N \times M$ 的矩形网格上。每个单元格完全属于其中一方。地球人可以制造炸弹,摧毁战场上某个矩形区域内的所有单元格,该区域的边与战场的边平行。炸弹不能旋转,也不能在战场范围外使用。炸弹可以使用无限次。

当然,人类不希望摧毁自己的单元格,但他们可以制造特定尺寸的炸弹。请计算炸弹的最大影响面积(即高度与宽度的乘积),使得该炸弹能够摧毁所有外星人的单元格,且不摧毁任何地球人的单元格。任何外星人的单元格都可以被多次摧毁。

输入格式

输入的第一行包含两个整数 $N, M$ ($1 \le N, M \le 2500$),用空格分隔,其中 $N$ 和 $M$ 分别为战场的高度和宽度。接下来有 $N$ 行,每行包含 $M$ 个符号,定义了战场。如果给定行中的符号为“0”,则对应的单元格属于地球人;如果符号为“1”,则对应的单元格属于外星人。

输出格式

输出一个整数,表示炸弹摧毁的最大面积。

子任务

本题共有 100 个测试点:

  1. 测试点 1-6:$N = 1$ 或 $M = 1$。
  2. 测试点 7-16:$1 \le N, M \le 20$。
  3. 测试点 17-26:$1 \le N, M \le 100$。
  4. 测试点 27-36:$1 \le N, M \le 450$。
  5. 测试点 37-100:$1 \le N, M \le 2500$。

每个通过的测试点得 1 分。

样例

样例输入 1

5 6
001000
111110
111110
111110
000100

样例输出 1

3

说明

在样例测试中,最优炸弹的尺寸为 $3 \times 1$。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.