結果

問題 No.866 レベルKの正方形
コンテスト
ユーザー LyricalMaestro
提出日時 2026-05-05 18:09:36
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
TLE  
実行時間 -
コード長 2,232 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 969 ms
コンパイル使用メモリ 201,316 KB
実行使用メモリ 450,596 KB
最終ジャッジ日時 2026-05-05 18:10:31
合計ジャッジ時間 11,016 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 8 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::{input, marker::Chars};

fn solve2(
    h: usize,
    w: usize,
    k: usize,
    l: usize,
    cum_dp_array: &Vec<Vec<Vec<i32>>>,
) -> 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<Vec<Vec<i32>>>,
) -> 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<Vec<i32>>> = 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);
}
0