use proconio::{input, marker::Chars}; fn solve2( h: usize, w: usize, k: usize, l: usize, cum_dp_array: &Vec>>, ) -> bool { let h1 = h + l - 1; let w1 = w + l - 1; let mut answer = 0usize; for word in 0..26 { let cum_dp = &cum_dp_array[word]; let ans = cum_dp[h1 + 1][w1 + 1] - cum_dp[h1 + 1][w] - cum_dp[h][w1 + 1] + cum_dp[h][w]; if ans > 0 { answer += 1; } } answer <= k } fn solve( h_size: usize, w_size: usize, k: usize, cum_dp_array: &Vec>>, ) -> usize { let mut answer = 0usize; for h in 0..h_size { for w in 0..w_size { let mut low = 1usize; let mut high = (h_size - h).min(w_size - w); while high - low > 1 { let mid = (high + low) / 2; if solve2(h, w, k, mid, cum_dp_array) { low = mid; } else { high = mid; } } if solve2(h, w, k, high, cum_dp_array) { answer += high; } else { answer += low; } } } answer } fn main() { input! { h_size: usize, w_size: usize, k: usize, c: [Chars; h_size], } let mut cum_dp_array: Vec>> = Vec::new(); for word in 0..26 { let mut dp = vec![vec![0i32; w_size]; h_size]; for h in 0..h_size { for w in 0..w_size { if (c[h][w] as u8 - b'a') as usize == word { dp[h][w] += 1; } } } let mut cum_dp = vec![vec![0i32; w_size + 1]; h_size + 1]; for h in 0..h_size { let mut row = 0i32; for w in 0..w_size { row += dp[h][w]; cum_dp[h + 1][w + 1] = cum_dp[h][w + 1] + row; } } cum_dp_array.push(cum_dp); } let mut ans = solve(h_size, w_size, k, &cum_dp_array); if k > 1 { let ans2 = solve(h_size, w_size, k - 1, &cum_dp_array); ans -= ans2; } println!("{}", ans); }