Submission #44704935

---

Source Code Expand

use itertools::Itertools;
use memoise::memoise;
use proconio::input;

fn main() {
    input! {
        n : usize,
        m : usize
    }

    let mut c = vec![];
    let mut s = vec![];

    for _ in 0..n {
        input! { ci : f64, si : [usize] }
        c.push(ci);
        s.push(si);
    }

    for i in 0..n {
        c[i] *= s[i].len() as f64;
        s[i] = s[i].iter().filter(|&&s| s != 0).cloned().collect_vec();
        c[i] /= s[i].len() as f64;
    }

    let ans = dp(m, &c, &s);
    println!("{}", ans);
}

#[memoise(m)]
fn dp(m:usize, c:&Vec<f64>, s:&Vec<Vec<usize>>) -> f64 {
    if m <= 0 { return 0.0; }

    let mut res = f64::MAX;

    for i in 0..c.len() {
        let mut e = c[i];
        for &sj in s[i].iter() {
            e += dp(m.saturating_sub(sj), c, s) / s[i].len() as f64;
        }

        res = res.min(e);
    }

    res
}

Submission Info

Judge Result