結果

問題 No.2429 Happiest Tabehodai Ways
コンテスト
ユーザー ずーずる
提出日時 2023-08-29 05:46:02
言語 Rust
(1.83.0 + proconio)
結果
MLE  
実行時間 -
コード長 3,678 bytes
コンパイル時間 19,512 ms
コンパイル使用メモリ 378,980 KB
実行使用メモリ 1,632,784 KB
最終ジャッジ日時 2024-12-30 21:42:23
合計ジャッジ時間 59,949 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 29 WA * 1 RE * 2 TLE * 8 MLE * 4
権限があれば一括ダウンロードができます

ソースコード

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