AtCoder Beginner Contest 441 F

https://atcoder.jp/contests/abc441/tasks/abc441_f

何番目の商品まで考慮したかとトータルの金額を状態にして、最大の価値を値にしたDPを考えると、計算量は $O(NM)$ なので、なんとか間に合います。
入力例1だと、最初は0円で価値も0なので、
[0, -∞, -∞, -∞, -∞, -∞, -∞, -∞]
とします。商品1を買う買わないで、
[0, -∞, 5, -∞, -∞, -∞, -∞, -∞]
となります。4つの商品までで、
[0, -∞, 5, 10, 10, 15, 15, 20]
最終的には、
[0, -∞, 5, 20, 10, 25, 30, 30]
となります。
問題はトレースバックです。まず最後の商品まで考慮したときの最大の価値を得て、その金額からDPの結果を逆に辿ります。そのときその商品を購入したときとしなかったときで、対応する金額に対して価値がDPの結果が合っていれば、それに応じてフラグを立てて、最終的にABCのどれか決めます。
入力例1だと、価値が30なので、金額は6と7です。金額6のとき、商品を買うとすると、最後の商品は金額3、価値20なので、金額6-3=3の前の値を見ると10なので、30-20と合っています。つまり金額3が最大パスの一つになっています。商品を買わないとすると、金額6は価値15なので、これは合わないです。金額7を見ると、商品を買うとすると、金額4を見ると価値は10なので、合っています。商品を買わないのは合いません。したがって、前の金額は3と4です。このように後ろ向きに辿ります。

このように最大の価値になる金額は複数あるかもしれないので、HashSetで金額を集めていたのですが、一部が時間オーバーになってしまいました。RustはHashSetがやたら遅いという話なので、BTreeSetにしてみましたが、あまり変わりませんでした。仕方がないのでVecを全部作ってどの金額が最大の価値になるかを調べるようにしてみたところ、余裕で通りました。

// Must Buy
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Item ////////////////////

type Item = (usize, i64);

fn read_item() -> Item {
    let v: Vec<usize> = read_vec();
    let (P, V) = (v[0], v[1] as i64);
    (P, V)
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<Item>) {
    let v: Vec<usize> = read_vec();
    let (N, M) = (v[0], v[1]);
    let items: Vec<Item> = (0..N).map(|_| read_item()).collect();
    (M, items)
}

use std::cmp::max;

fn update_dp(i: usize, item: Item, dp: &mut Vec<Vec<i64>>) {
    let M = dp[0].len() - 1;
    for j in 0..M+1 {
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])      // itemを買わない
    }
    for j in item.0..M+1 {
        dp[i+1][j] = max(dp[i][j-item.0]+item.1, dp[i+1][j])    // itemを買う
    }
}

fn trace_back(dp: Vec<Vec<i64>>, items: Vec<Item>) -> String {
    let N = dp.len() - 1;
    let M = dp[0].len() - 1;
    let mut v: Vec<char> = vec!['A'; N];
    let max_value = *dp[N].iter().max().unwrap();
    let mut ms: Vec<usize> = (0..M+1).filter(|&m| dp[N][m] == max_value).
                                                                collect();
    for i in (0..N).rev() {
        let mut flags: u32 = 0;     // 買うが上ビット、買わないが下ビット
        let item = items[i];
        let mut used: Vec<bool> = vec![false; M+1];
        for m in ms {
            // itemを買わない
            if dp[i][m] == dp[i+1][m] {
                flags |= 1;
                used[m] = true
            }
            if m >= item.0 && dp[i][m-item.0] + item.1 == dp[i+1][m] {
                flags |= 2;
                used[m-item.0] = true
            }
        }
        v[i] = match flags {
                    1 => 'C',
                    2 => 'A',
                    _ => 'B'
        };
        ms = (0..M+1).filter(|&m| used[m]).collect()
    }
    v.into_iter().collect::<String>()
}

fn F(M: usize, items: Vec<Item>) -> String {
    let N = items.len();
    let mut dp: Vec<Vec<i64>> = vec![vec![i64::MIN; M+1]; N+1];
    dp[0][0] = 0;
    for i in 0..N {
        update_dp(i, items[i], &mut dp)
    }
    trace_back(dp, items)
}

fn main() {
    let (M, items) = read_input();
    println!("{}", F(M, items))
}