コイン集め 2 (Coin Collecting 2)
시간 제한2초메모리 제한1024 MB
아오이가 한 행을, 린이 한 열을 뒤집은 뒤 보이는 면에 따라 코인을 나눠 가질 때, 두 사람이 최선을 다하면 각각 몇 개를 얻는지 구한다.
문제
机の上に，縦 H 行，横 W 列の長方形状にコインが並べられている． 最初，上から i 行目 (1 ≦ i ≦ H)，左から j 列目 (1 ≦ j ≦ W) のコインは， Si,j= # のとき表面，Si,j= . のとき裏面が見えている状態である．
葵と凛は，これらのコインを用いてゲームを行うことにした．ゲームは以下のような流れで行われる．
- 葵がどれか
1つの行を選び，その行のコインをすべてひっくり返す． - 凛がどれか
1つの列を選び，その列のコインをすべてひっくり返す． - 葵が，表面が見えるコインをすべて獲得する．また凛が，裏面が見えるコインをすべて獲得する．
葵と凛はそれぞれ，できるだけ多くのコインを獲得したい．
ゲーム開始時のコインの状態が与えられたとき， 両者が最善を尽くした場合にそれぞれが獲得できるコインの枚数を求めるプログラムを作成せよ．
입력
入力は以下の形式で与えられる．
H W
S1,1 S1,2 … S1,W
S2,1 S2,2 … S2,W
︙
SH,1 SH,2 … SH,W
출력
葵と凛の得点をこの順に空白区切りで出力せよ．
제한
H ≧ 1．W ≧ 1．H × W ≦ 500 000．Si, jは#，.のいずれかである (1 ≦ i ≦ H，1 ≦ j ≦ W)．H, Wは整数である．