結果

問題 No.269 見栄っ張りの募金活動
ユーザー kinodjnz
提出日時 2025-04-10 12:49:59
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 26 ms / 5,000 ms
コード長 1,551 bytes
コンパイル時間 11,999 ms
コンパイル使用メモリ 404,076 KB
実行使用メモリ 18,176 KB
最終ジャッジ日時 2025-04-10 12:50:16
合計ジャッジ時間 13,657 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::Read;

const M: usize = 1000000007;

fn solve(n: usize, s: i64, k: i64) -> usize {
    // dp[i][j] = i番目以降が総額l円になる組み合わせ数
    let mut dp = vec![vec![0; (s + 1) as usize]; n];
    for j in 0..=s {
        dp[n - 1][j as usize] = 1;
    }
    // k = 1 の場合
    // dp[2] = [1, 1, 1, 1, 1, 1, ]
    // dp[1] = [0, 1, 1, 1, 1, 1, ] // +1円 = +(0+(0+k)*w)
    //       + [0, 0, 0, 1, 1, 1, ] // +3円 = +(1+(1+k)*w)
    //       + [0, 0, 0, 0, 0, 1, ] // +5円 = +(2+(2+k)*w)
    //       = [0, 1, 1, 2, 2, 3, ]
    // dp[0] = [0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, ] // +2円 = +(0+(0+k)*w)
    //       + [0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, ] // +5円 = +(1+(1+k)*w)
    //       + [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, ] // +8円 = +(2+(2+k)*w)
    for i in (0..n - 1).rev() {
        let mut v = vec![0; (s + 1) as usize];
        let w = (n - i - 1) as i64;
        for j in k * w..=s {
            let l = ((j - k * w) % (w + 1)) as usize;
            v[l] = (v[l] + dp[i + 1][(j - k * w) as usize]) % M;
            dp[i][j as usize] = v[l];
        }
        // println!("dp[{}] = {:?}", i, &dp[i]);
    }
    dp[0][s as usize]
}

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n: usize = iter.next().unwrap().parse().unwrap();
    let s: i64 = iter.next().unwrap().parse().unwrap();
    let k: i64 = iter.next().unwrap().parse().unwrap();
    let result = solve(n, s, k);
    println!("{}", result);
}
0