https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5654760

DSL_1_G.rs

#![allow(non_snake_case, dead_code)]

#[fastout]
fn main() {
  input! {
    N: usize, mut W: Weight,
    mut X: [(Value, Weight, Count); N],
  }

  let mut Y = vec![vec![]; 20];
  let mut Z = 0;
  for (i, (_w, v, m)) in X.iter_mut().enumerate() {
    Z += 4 * *v;
    let mut a = 1;
    let mut b = 1;
    while a * 2 < *m {
      a = a * 2 + 1;
      b += 1;
    }
    *m -= a;
    for j in 0 .. b {
      if (*m >> j & 1) != 0 {
        Y[j].push(i);
      }
      Y[j].push(i);
    }
  }

  let mut DPnow = vec![0; Z + 1];
  let mut DPnext = vec![-INF; Z + 1];
  DPnext[0] = 0;
  for t in 0 .. 20 {
    for j in 0 .. Y[t].len() {
      swap(&mut DPnow, &mut DPnext);
      for x in &mut DPnext {
        *x = -INF;
      }
      let x = Y[t][j];
      for k in 0 ..= Z {
        DPnext[k] = DPnext[k].max(DPnow[k]);
        if k + X[x].1 <= Z {
          DPnext[k + X[x].1] = DPnext[k + X[x].1].max(DPnow[k] + (X[x].0 << t ));
        }
      }
    }
    let mut x = vec![-INF; Z + 1];
    for j in 0 ..= Z {
      if W >= j {
        x[(W >> 1) - (W - j >> 1)] = x[(W >> 1) - (W - j >> 1)].max(DPnext[j]);
      }
    }
    DPnext = x;
    W >>= 1;
  }

  let ans = DPnext[0 ..= Z.min(W)].into_iter().max().unwrap();
  println!("{}", ans);
}

const INF: Value = 1_000_000_000_000_000_000;

type Value = i64;
type Weight = usize;
type Count = usize;

use proconio::{input, fastout};
use std::mem::*;