题目详情题解（0）讨论（0）提交记录（0）

AT_arc081_d.[ARC081F] Flip and Rectangles

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个 H×WH \times W 的网格。网格中的每个格子被涂成黑色或白色。从上到下第 ii 行，从左到右第 jj 列的格子，如果 SiS_i 的第 jj 个字符是 #，那么该格子是黑色；如果是 .，那么是白色。

Sunnuke 君可以任意次数地进行如下操作：

  • 任选网格中的某一行或某一列，将该行或该列的所有格子的颜色反转（即，将黑色格子变成白色，将白色格子变成黑色）。

在操作结束后，Sunnuke 君会选择网格中的一个长方形。此时，所选长方形中的所有格子必须都是黑色。

若操作合理，Sunnuke 君能选择的长方形的最大面积是多少？

输入格式

输入以如下格式从标准输入中给出。

HH WW
S1S_1
S2S_2
⋮\vdots
SHS_H

输出格式

输出 Sunnuke 君能选择的最大长方形的面积。

输入输出样例

  • 输入#1

    3 3
..#
##.
.#.

    输出#1

    6

  • 输入#2

    4 4
....
....
....
....

    输出#2

    16

  • 输入#3

    10 8
##...#.#
##...#.#
..###.#.
#.##.#.#
.#..#.#.
..##.#.#
##.#.#..
...#.#..
###.#.##
###..###

    输出#3

    27

说明/提示

限制条件

  • 2≤H≤20002 \leq H \leq 2000
  • 2≤W≤20002 \leq W \leq 2000
  • ∣Si∣=W|S_i| = W
  • SiS_i 仅由 # 和 . 组成。

样例说明 1

如图所示，如果将第 1 行和第 3 列进行反转，则可以选出一个 2×32 \times 3 的长方形。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页