Submission #60544137

---

Source Code Expand

#[allow(unused_imports)]
use proconio::{input, marker::Usize1};

fn main() {
    input!{
        n: usize,
        x: usize,
        k: i64,
        mut items: [(usize, i64, Usize1); n],
    }
    let items = items.iter()
        .fold(vec![vec![]; n], |mut v, &(p, u, c)| {
            v[c].push((p, u));
            v
    });
    let inf :i64 = -1;
    let mut dp =vec![vec![inf; x+1]; 2];
    let mut cur = 0;
    dp[cur][0] = 0;
    for v in items.iter() {
        if v.is_empty() {
            continue;
        }
        let nxt = 1 - cur;
        for &(p, u) in v.iter() {
            for i in (0..=x).rev() {
                if dp[cur][i] != inf {
                    // 買わない
                    let val = dp[cur][i];
                    dp[nxt][i].chmax(val);
                }
                if i + p > x {
                    continue;
                }

                // cur -> nxt (k)
                if dp[cur][i] != inf {
                    let val = dp[cur][i] + u + k;
                    dp[nxt][i+p].chmax(val);

                }
                // nxt -> nxt
                if dp[nxt][i] != inf {
                    let val = dp[nxt][i] + u;
                    dp[nxt][i+p].chmax(val);
                }
            }
        }
        dp[cur].fill(inf);
        cur = nxt;
    }
    println!("{}", dp[cur].iter().max().unwrap());
}

pub trait ChLibs<T: std::cmp::Ord> {
    fn chmin(&mut self, elm: T) -> bool;
    fn chmax(&mut self, elm: T) -> bool;
}

impl<T: std::cmp::Ord> ChLibs<T> for T {
    fn chmin(&mut self, elm: T) -> bool {
        if *self > elm {
            *self = elm;
            true
        } else {
            false
        }
    }

    fn chmax(&mut self, elm: T) -> bool {
        if *self < elm {
            *self = elm;
            true
        } else {
            false
        }
    }
}
pub trait Debuggable {
    fn debug_string(&self) -> String;
}

impl<T: std::fmt::Debug + std::fmt::Display> Debuggable for Vec<T> {
    fn debug_string(&self) -> String {
        use itertools::Itertools;
        use std::iter::repeat;
        if let Some(max_size) = self.iter()
            .map(|x| format!("{:?}", x).len())
            .max() {
                let mut idx = String::from("idx |");   
                let mut val = String::from("val |");   
                for (i, xi) in self.iter().enumerate() {
                    idx.push_str(
                        &format!(" {:>w$} |", i, w=max_size)
                    );
                    val.push_str(
                        &format!(" {:>w$} |", xi, w=max_size)
                    );
                }

                format!("{}\n{}\n{}\n", idx, repeat('-').take(idx.len()).join(""), val)
            } else {
                format!("idx | \nval |\n")
            }
    }
}

impl<T: std::fmt::Debug + std::fmt::Display> Debuggable for std::collections::BTreeSet<T> {
    fn debug_string(&self) -> String {
        use itertools::Itertools;
        format!("{{ {} }}", self.iter().join(", "))
    }
}

impl<T, U> Debuggable for std::collections::BTreeMap<T, U> 
where T: std::fmt::Debug + std::fmt::Display, U: std::fmt::Debug + std::fmt::Display
{
    fn debug_string(&self) -> String {
        use itertools::Itertools;
        format!(
            "{{\n{}\n }}", self.iter()
                .map(|(k, v)| format!("{k} -> {v}, "))
                .join("\n")
        )
    }
}

// lg! マクロの定義
#[macro_export]
macro_rules! lg {
    ($val:expr) => {
        #[cfg(feature = "local")]
        {
            {
                use Debuggable;
                let val = &$val;
                eprintln!(
                    "[{}:{}] {} = \n{}",
                    file!(),
                    line!(),
                    stringify!($val),
                    val.debug_string()
                );
                val
            }
        }
    }
}
    

Submission Info

Judge Result