AT_joig2023_d.コイン集め 2 (Coin Collecting 2)

在桌子上，按纵向 $H$ 行、横向 $W$ 列排放着若干个矩形排列的硬币。最初，从上到下第 $i$ 行（$1 \leq i \leq H$），从左到右第 $j$ 列（$1 \leq j \leq W$）的硬币，如果 $S_{i,j}=$ #，则为正面朝上；如果 $S_{i,j}=$ .，则为反面朝上。

葵和凛决定用这些硬币玩一个游戏。游戏流程如下：

1. 葵选择任意一行，将该行所有硬币全部翻面。
2. 凛选择任意一列，将该列所有硬币全部翻面。
3. 最后，葵获得所有正面朝上的硬币，凛获得所有反面朝上的硬币。

葵与凛都会尽可能多地获得硬币。

给定游戏开始时所有硬币的状态，请编写程序求出二人在均采取最优策略情况下，各自能获得多少硬币。

输入格式如下：

$H$ $W$
$S_{1,1}$ $S_{1,2}$ $\cdots$ $S_{1,W}$
$S_{2,1}$ $S_{2,2}$ $\cdots$ $S_{2,W}$
$\vdots$
$S_{H,1}$ $S_{H,2}$ $\cdots$ $S_{H,W}$

请按顺序输出葵和凛各自的得分，用空格分隔。

子任务

1. （$2$ 分）$H=1$, $W=1$。
2. （$8$ 分）$H=1$, $W \leq 40$。
3. （$9$ 分）$H \leq 40$, $W=1$。
4. （$14$ 分）$H=2$, $W=2$。
5. （$23$ 分）$H \leq 40$, $W \leq 40$。
6. （$18$ 分）$H \leq 250$, $W \leq 250$。
7. （$26$ 分）无额外限制。

样例解释 1

对于该输入，无论怎样游戏都必然如下进行：

1. 首先，葵将第 $1$ 行的所有硬币翻面。
2. 接着，凛将第 $1$ 列的所有硬币翻面。

此时，唯一的硬币面朝现状为“正→反→正”，因此葵能获得 $1$ 枚硬币，凛无法获得硬币。因此，按顺序输出 $1$、$0$，中间用空格分隔。

此外，该输入满足子任务 $1, 2, 3, 5, 6, 7$ 的限制。

样例解释 2

两人均采用最优策略时，游戏过程的一种示例如下图：

该输入满足子任务 $5, 6, 7$ 的限制。

样例解释 3

该输入满足子任务 $2, 5, 6, 7$ 的限制。

样例解释 4

该输入满足子任务 $3, 5, 6, 7$ 的限制。

样例解释 5

该输入满足子任务 $5, 6, 7$ 的限制。

样例解释 6

该输入满足子任务 $5, 6, 7$ 的限制。

数据范围

• $H \geq 1$。
• $W \geq 1$。
• $H \times W \leq 500\,000$。
• $S_{i,j}$ 为 # 或 .，其中 $1 \leq i \leq H$，$1 \leq j \leq W$。
• $H,W$ 为整数。

由 ChatGPT 5 翻译