← 返回题目列表

AtCoder · joig2023_d

D. 硬币收集 2

中文机器翻译题面 查看原题

配点: 100 点

問題文

张桌子上以纵向 H 行,横 W 列的矩形排列着硬币。 最初,从上到下第 i 行目 (1 \leqq i \leqq H行,从左到右第 j 列目 (1 \leqq j \leqq W列的硬币,在 S_{i,j}= # 时是正面,在S_{i,j}= . 时是背面。

葵和凛决定用这些硬币玩一个游戏。游戏按照以下流程进行。

  1. 葵选择某个 1 选择一行并翻转该行上的所有硬币。
  2. 哪一个是凛? 1 选择一列并翻转该列中的所有硬币。
  3. 葵获得所有带有可见面孔的硬币。凛还获得了所有背面可见的硬币。

葵和凛都想赚取尽可能多的金币。

鉴于游戏开始时硬币的状态, 编写一个程序来找出如果双方都尽力而为的话,双方可以获得的硬币数量。 是

制約

  • H \geqq 1.
  • W \geqq 1.
  • H \times W \leqq 500\,000.
  • S_{i, j} 是 #,. (1 \leqq i \leqq H,1 \leqq j \leqq W).
  • H, W 是一个整数。

小課題

  1. (2 点) H = 1,W = 1.
  2. (8 点) H = 1,W \leqq 40.
  3. (9 点) H \leqq 40,W = 1.
  4. (14 点) H = 2,W = 2.
  5. (23 点) H \leqq 40,W \leqq 40.
  6. (18 点) H \leqq 250,W \leqq 250.
  7. (26 点)没有额外的限制。

入力

输入按以下格式给出。

H W
S_{1,1}S_{1,2}\cdotsS_{1,W}
S_{2,1}S_{2,2}\cdotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\cdotsS_{H,W}

出力

按顺序输出 Aoi 和 Rin 的分数,以空格分隔。


入力例 1

1 1
#

出力例 1

1 0

在此输入示例中,游戏将始终按如下方式进行。

  1. 首先,葵 1 翻转行中的所有硬币。
  2. 接下来,凛 1 翻转该列中的所有硬币。

此时,硬币唯一可见的一面从“正面→反面→正面”发生变化,所以葵 你可以获得 1 金币,但凛无法获得任何金币。因此, 按此顺序输出1,0 ,用空格分隔。

此输入示例是一个小作业。 1, 2, 3, 5, 6, 7 满足约束。


入力例 2

5 5
#####
####.
###..
##...
#....

出力例 2

13 12

下图显示了当双方都尽力而为时游戏如何进展的示例。

此输入示例是一个小作业。 5, 6, 7 满足约束。


入力例 3

1 40
..........##########..........##########

出力例 3

19 21

此输入示例是一个小作业。 2, 5, 6, 7 满足约束。


入力例 4

7 1
#
#
#
#
#
#
#

出力例 4

1 6

此输入示例是一个小作业。 3, 5, 6, 7 满足约束。


入力例 5

5 5
.###.
...##
..##.
.##..
##...

出力例 5

11 14

此输入示例是一个小作业。 5, 6, 7 满足约束。


入力例 6

10 40
........................................
..######.....####.....#####.....####....
.....#......#....#......#......#........
.....#......#....#......#......#........
.....#......#....#......#......#........
.....#......#....#......#......#..####..
..#..#......#....#......#......#....#...
..#..#......#....#......#......#....#...
...##........####.....#####.....####....
........................................

出力例 6

104 296

此输入示例是一个小作业。 5, 6, 7 满足约束。