Skip to main content

aizu_online_judge/dpl/
dpl_1_f.rs

1use competitive::combinatorial_optimization::KnapsackProblemSmallValue;
2use competitive::prelude::*;
3
4#[verify::aizu_online_judge("DPL_1_F")]
5pub fn dpl_1_f(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, w: i64, vw: [(usize, i64); n]);
8    let mut knapsack = KnapsackProblemSmallValue::new(vw.iter().map(|&(v, _)| v).sum::<usize>());
9    knapsack.extend01(vw);
10    pp!(knapsack.solve(w).unwrap_or_default());
11}