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 翻译