Submission #72562876

---

Source Code Expand

#![allow(non_snake_case, unused_imports, unused_macros)]
use std::{collections::BTreeSet, mem::needs_drop};

use ac_library::*;
use itertools::Itertools;
use proconio::{fastout, input};
use rustc_hash::FxHashSet;

macro_rules! debug {
    ($($a:expr),* $(,)*) => {
        #[cfg(debug_assertions)]
        eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*);
    };
}

#[fastout]
fn main() {
    input! {
        n: usize, m: usize,
        pv: [(usize, usize); n]
    }
    let mut dp = vec![vec![None::<usize>; m + 1]];
    dp[0][0] = Some(0);

    for (i, &(pi, vi)) in pv.iter().enumerate() {
        let next_dp = (0..=m)
            .map(|p| {
                dp[i][p].max(
                    dp[i]
                        .get(p.wrapping_sub(pi))
                        .copied()
                        .flatten()
                        .map(|v| v + vi),
                )
            })
            .collect_vec();
        dp.push(next_dp);
    }
    // debug!(dp);
    let mut must_buy = vec![false; n];
    let mut may_buy = vec![false; n];

    let maxarg_v = (0..=m).max_set_by_key(|&p| dp[n][p]);
    let mut prices = FxHashSet::from_iter(maxarg_v);
    for (i, &(pi, vi)) in pv.iter().enumerate().rev() {
        // debug!(prices, i, pi, vi);
        let mut next_prices = FxHashSet::default();
        let mut may_not_buy = false;
        for price in prices {
            if price >= pi
                && let Some(v) = dp[i][price - pi]
                && v + vi == dp[i + 1][price].unwrap()
            {
                next_prices.insert(price - pi);
                may_buy[i] = true;
            }
            if let Some(v) = dp[i][price]
                && v == dp[i + 1][price].unwrap()
            {
                next_prices.insert(price);
                may_not_buy = true;
            }
        }
        must_buy[i] = !may_not_buy;
        prices = next_prices;
    }

    for i in 0..n {
        if must_buy[i] {
            print!("A");
        } else if may_buy[i] {
            print!("B");
        } else {
            print!("C")
        }
    }
}

Submission Info

Judge Result