Vitamin Balance の解説

ビタミン1, 2, 3で分けて考える。

dp[i][j] := i番目までみてカロリーjで取得できるビタミンの最大値

としてそれぞれ取得、あとはビタミン1, 2で取得するカロリーを全探索してあげて答えを取得する...だけ！！

fn main() {
    input! {
        n: usize,
        x: usize,
        vac: [(usize, isize, usize); n]
    }
    let f = |target: usize| {
        let vac = vac.iter().filter(|&&e| e.0 == target).collect_vec();
        let n = vac.len();
        let mut dp = vec![vec![-1; x + 1]; n + 1];
        dp[0][0] = 0;

        for i in 0..n {
            for j in 0..=x {
                if dp[i][j] == -1 {
                    continue;
                }
                let now = dp[i][j];
                let &(_v, a, c) = vac[i];

                dp[i + 1][j].chmax(now);
                if j + c <= x {
                    dp[i + 1][j + c].chmax(now + a);
                }
            }
        }
        dp[n].to_owned()
    };

    let one = Segtree::<Max<isize>>::from(f(1));
    let two = Segtree::<Max<isize>>::from(f(2));
    let three = Segtree::<Max<isize>>::from(f(3));

    let mut ans = 0;
    for a in 0..=x {
        for b in 0..=x {
            if a + b > x {
                continue;
            }
            let c = x - a - b;

            let one = one.prod(..=a);
            let two = two.prod(..=b);
            let three = three.prod(..=c);
            ans = max(min(one, two).min(three), ans);
        }
    }
    println!("{}", ans);
}