結果

問題 No.2429 Happiest Tabehodai Ways
ユーザー ずーずるずーずる
提出日時 2023-08-29 05:46:02
言語 Rust
(1.77.0 + proconio)
結果
MLE  
実行時間 -
コード長 3,678 bytes
コンパイル時間 15,551 ms
コンパイル使用メモリ 394,500 KB
実行使用メモリ 809,104 KB
最終ジャッジ日時 2024-06-09 20:37:16
合計ジャッジ時間 19,275 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

// use rustc_hash::FxHashMap;
use std::collections::HashMap;
fn main() {
    let v = read_split_parse();
    let n: u128 = v[0];
    let k = v[1];
    let full: Vec<u128> = read_split_parse();
    let happy: Vec<u128> = read_split_parse();
    let f_h: Vec<_> = full.into_iter().zip(happy.into_iter()).collect();
    let div = 998244353;
    let mut dp_way: HashMap<(u128, u128), (u128, Vec<HashMap<u128, u128>>)> = HashMap::new();
    // dp(i,j)はi番目以降の飯だけ食って、今の満腹度がjのときMaxどのくらいhappyかと
    // それを満たす食べ方のSet、つまり
    // hashmap ( k->l )= k番目の料理はlこ食べる
    for i in 0..=k {
        dp_way.insert((n, i), (0u128, vec![]));
    }

    for i in 0..=n {
        dp_way.insert((i, k), (0u128, vec![]));
    }

    for i in (1..=n).rev() {
        // jは今の満腹どあい
        for j in 0..=k {
            // 次に食べるかもしれない飯の満腹度合い
            let volume = f_h[i as usize - 1].0;
            let happy = f_h[i as usize - 1].1;

            let mut full = j;
            let mut candidate = vec![];
            candidate.push(dp_way.get(&(i, j)).unwrap().clone());
            let mut n = 0u128;

            loop {
                full += volume;
                n += 1;
                if full <= k {
                    let mut new_set = dp_way.get(&(i, full)).unwrap().1.clone();
                    if new_set.is_empty() {
                        let mut c=HashMap::new();
                        c.insert(i - 1, n);
                        new_set.push(c);
                    } else {
                        for item in new_set.iter_mut() {
                            item.insert(i - 1, n);
                        }
                    }
                    candidate.push((dp_way.get(&(i, full)).unwrap().0 + happy * n, new_set));
                } else {
                    break;
                }
            }

            let max = candidate.iter().max_by_key(|x| x.0).unwrap().0;
            let good = candidate.iter().filter(|x| x.0 == max);
            let mut new_vec = vec![];
            for it in good {
                new_vec.extend(it.1.clone());
            }

            // println!("{}",new_vec.len());
            dp_way.insert((i - 1, j), (max, new_vec));
        }
    }
    // println!("{:?}",dp_way.iter().filter(|x|x.1.0==37).collect::<Vec<_>>());
    println!("{}", dp_way.get(&(0, 0)).unwrap().0);
    // println!("{}", dp_way.get(&(0, 0)).unwrap().1 % div);
    let mut ways = 0;
    for i in dp_way.get(&(0, 0)).unwrap().1.iter() {
        let mut len = 0;
        let mut tmp=1;
        for j in i {
            len += j.1;
            tmp*=fac(*j.1);
        }
        ways+=fac(len)/tmp;

        // let mut tmp = vec![];
        // for j in i {
        //     len += j.1;
        //     tmp.push(fac(*j.1));
        // }
        // let mut it=tmp.iter().peekable();

        // let mut f=1;
        // for i in 1..=len{
        //     f*=i;
            
        // }

        // ways = ways + ( f/ tmp)%div;


    }
    if ways==0{
        println!("1");
    }else{
        println!("{}", ways % div);
    }
}

fn fac(n: u128) -> u128 {
    if n == 1 {
        return 1;
    }
    return n * fac(n - 1);
}

use std::fmt::Debug;
use std::str::FromStr;


fn read_line() -> String {
    use std::io;
    let mut x = String::new();
    io::stdin().read_line(&mut x).unwrap();
    x
}

fn read_split_parse<T>() -> Vec<T>
where
    T: Clone + FromStr,
    <T as FromStr>::Err: Debug,
{
    read_line()
        .split_whitespace()
        .map(|a| a.parse::<T>().unwrap())
        .collect::<Vec<T>>()
}
0