aizu_online_judge/dpl/dpl_1_i.rs
1use competitive::combinatorial_optimization::ZeroOneKnapsackProblemBranchAndBound;
2use competitive::prelude::*;
3
4#[verify::aizu_online_judge("DPL_1_I")]
5pub fn dpl_1_i(reader: impl Read, writer: impl Write) {
6 prepare_io!(reader, writer);
7 sc!(n, w: i64, vwm: [(i64, i64, i64); iter n]);
8 let mut item = vec![];
9 for (v, w, mut m) in vwm {
10 let mut b = 1;
11 while m > 0 {
12 let k = b.min(m);
13 m -= k;
14 item.push((v * k, w * k));
15 b *= 2;
16 }
17 }
18 let knapsack = ZeroOneKnapsackProblemBranchAndBound::new(item);
19 pp!(knapsack.solve(w));
20}