Maximum Glutton の解説

類題：https://atcoder.jp/contests/abc410/tasks/abc410_e

dp[i][j][k] := i番目の料理までを見たときに、甘さがj, 料理をkこ食べたときのしょっぱさの最小値

としてdpする。

こんな感じで2変数あるなら片方を値としてもっちゃうdpを思いつけさえすれば簡単に解ける。

しょっぱさが超えたときに、食べるのをやめるので、全部食べれる以外のときは食べれなくなる最大値 + 1が答えとなることに注意。

fn main() {
    input! {
        n: usize,
        x: usize,
        y: usize,
        ab: [(usize, usize); n]
    }
    let ans1 = {
        let mut dp = vec![vec![vec![usize::MAX; n + 1]; x + 1]; n + 1];
        dp[0][0][0] = 0;
        for i in 0..n {
            for j in 0..=x {
                for k in 0..=n {
                    if dp[i][j][k] == usize::MAX {
                        continue;
                    }
                    let now = dp[i][j][k];
                    dp[i + 1][j][k].chmin(now);
                    let (a, b) = ab[i];
                    if j + a <= x && now + b <= y {
                        dp[i + 1][j + a][k + 1].chmin(now + b);
                    }
                }
            }
        }
        dp
    };
    let mut ans = 0;

    for j in 0..=x {
        for k in 0..=n {
            if ans1[n][j][k] == usize::MAX {
                continue;
            }
            ans = max(ans, k);
        }
    }
    if ans == n {
        return println!("{}", n);
    }

    println!("{}", ans + 1);
}