AtCoder Beginner Contest 431 D

https://atcoder.jp/contests/abc431/tasks/abc431_d

BodyのWeightを状態、トータルの嬉しさを値にしてDPすればよいです。最大でもですが、余裕で間に合っています。

// Robot Customize
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Part ////////////////////

struct Part {
    W: usize,
    H: i64,
    B: i64
}

impl Part {
    fn read() -> Part {
        let v: Vec<i64> = read_vec();
        Part { W: v[0] as usize, H: v[1], B: v[2] }
    }
}


//////////////////// process ////////////////////

fn read_input() -> Vec<Part> {
    let N: usize = read();
    (0..N).map(|_| Part::read()).collect::<Vec<_>>()
}

type DP = Vec<i64>;     // BodyのWeight -> トータルの嬉しさ

fn initialize_dp() -> DP {
    vec![0]
}

use std::cmp::max;

fn update_dp(part: Part, dp: DP) -> DP {
    let mut new_dp: DP = vec![0; dp.len()+part.W];
    for w in 0..dp.len() {
        new_dp[w] = max(dp[w] + part.H, new_dp[w]);
        new_dp[w+part.W] = max(dp[w] + part.B, new_dp[w+part.W]);
    }
    new_dp
}

fn F(parts: Vec<Part>) -> i64 {
    let total_weights = parts.iter().map(|p| p.W).sum::<usize>();
    let mut dp = initialize_dp();
    for part in parts {
        dp = update_dp(part, dp)
    }
    dp[(total_weights+1)/2..].into_iter().cloned().max().unwrap()
}

fn main() {
    let parts = read_input();
    println!("{}", F(parts))
}