配点: 100 点
問題文
张桌子上以纵向 H 行,横 W 列的矩形排列着硬币。
最初,从上到下第 i 行目 (1 \leqq i \leqq H行,从左到右第 j 列目 (1 \leqq j \leqq W列的硬币,在
S_{i,j}= # 时是正面,在S_{i,j}= . 时是背面。
葵和凛决定用这些硬币玩一个游戏。游戏按照以下流程进行。
- 葵选择某个 1 选择一行并翻转该行上的所有硬币。
- 哪一个是凛? 1 选择一列并翻转该列中的所有硬币。
- 葵获得所有带有可见面孔的硬币。凛还获得了所有背面可见的硬币。
葵和凛都想赚取尽可能多的金币。
鉴于游戏开始时硬币的状态, 编写一个程序来找出如果双方都尽力而为的话,双方可以获得的硬币数量。 是
制約
- 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 是一个整数。
小課題
- (2 点) H = 1,W = 1.
- (8 点) H = 1,W \leqq 40.
- (9 点) H \leqq 40,W = 1.
- (14 点) H = 2,W = 2.
- (23 点) H \leqq 40,W \leqq 40.
- (18 点) H \leqq 250,W \leqq 250.
- (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 翻转该列中的所有硬币。
此时,硬币唯一可见的一面从“正面→反面→正面”发生变化,所以葵 你可以获得 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 满足约束。