D - コイン集め 2 (Coin Collecting 2)
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点： 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}
出力
葵と凛の得点をこの順に空白区切りで出力せよ．
入力例 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 の制約を満たす．