use proconio::{input, marker::Chars}; fn main() { input! { n: usize, s: [Chars; n], } let calc = |l: usize, r: usize| r * r.saturating_sub(1) / 2 - l * l.saturating_sub(1) / 2; let mut ans = 0usize; let mut count = vec![]; for s in &s { let mut cnt = 0usize; let mut sum = 0; for j in 0..2 * n { if s[j] == '.' { cnt += 1; sum += j; } } ans += sum - calc(0, cnt); count.push(cnt); } for i in 0..n { if count[i] == n { continue; } while count[i] > n { let j = (i..n).find(|&j| count[j] < n).unwrap(); let c = (count[i] - n).min(n - count[j]); let cost = (j - i) * c + calc(count[i] - c, count[i]) - calc(count[j], count[j] + c); ans += cost; count[i] -= c; count[j] += c; } while count[i] < n { let j = (i..n).find(|&j| count[j] > n).unwrap(); let c = (count[j] - n).min(n - count[i]); let cost = (j - i) * c + calc(count[j] - c, count[j]) - calc(count[i], count[i] + c); ans += cost; count[i] += c; count[j] -= c; } } println!("{ans}"); }