aizu_online_judge/dpl/
dpl_1_i.rs

1#[doc(no_inline)]
2pub use competitive::combinatorial_optimization::ZeroOneKnapsackPloblemBranchAndBound;
3use competitive::prelude::*;
4
5#[verify::aizu_online_judge("DPL_1_I")]
6pub fn dpl_1_i(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, w: i64, vwm: [(i64, i64, i64)]);
10    let mut item = vec![];
11    for (v, w, mut m) in vwm.take(n) {
12        let mut b = 1;
13        while m > 0 {
14            let k = b.min(m);
15            m -= k;
16            item.push((v * k, w * k));
17            b *= 2;
18        }
19    }
20    let knapsack = ZeroOneKnapsackPloblemBranchAndBound::new(item);
21    writeln!(writer, "{}", knapsack.solve(w)).ok();
22}