結果

問題 No.3391 Line up Dominoes
コンテスト
ユーザー titia
提出日時 2025-12-17 03:20:58
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 937 ms / 3,000 ms
コード長 1,539 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 11,711 ms
コンパイル使用メモリ 404,576 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-17 03:21:34
合計ジャッジ時間 34,010 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::io::{self, Read};

const MOD: i64 = 998244353;

fn main() {
    // 入力の高速読み込み
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut it = input.split_whitespace();

    let n: usize = it.next().unwrap().parse().unwrap();
    let m: usize = it.next().unwrap().parse().unwrap();
    let k: i64 = it.next().unwrap().parse().unwrap();

    let mut a: Vec<i64> = (0..n)
        .map(|_| it.next().unwrap().parse().unwrap())
        .collect();

    // A.sort()
    a.sort();

    // MAX 配列
    let mut max_idx = vec![0usize; n];
    let mut ind = 0usize;
    for i in 0..n {
        while ind < n && a[ind] - a[i] <= k {
            ind += 1;
        }
        max_idx[i] = ind;
    }

    // MIN 配列
    let mut min_idx = vec![0usize; n];
    ind = 0;
    for i in 0..n {
        while ind < n && a[i] - a[ind] > k {
            ind += 1;
        }
        min_idx[i] = ind;
    }

    // DP 初期化
    let mut dp = vec![1i64; n];

    // DP 遷移を M-1 回
    for _ in 0..(m - 1) {
        // 累積和 S
        let mut s = vec![0i64; n + 1];
        for i in 0..n {
            s[i + 1] = (s[i] + dp[i]) % MOD;
        }

        // 次の DP
        let mut next_dp = vec![0i64; n];
        for j in 0..n {
            let val = s[max_idx[j]] - s[min_idx[j]];
            next_dp[j] = (val % MOD + MOD) % MOD;
        }
        dp = next_dp;
    }

    // 答え
    let ans: i64 = dp.iter().fold(0, |acc, &x| (acc + x) % MOD);
    println!("{}", ans);
}
0