アルゴリズムと数学 096

https://atcoder.jp/contests/math-and-algorithm/tasks/abc204_d

2つに分けてトータル時間が半分に近くなればよいですが、どの時間が実現可能かはDPで簡単に分かるので、半分以上で半分に近い実現可能な時間を探せばよいです。

// Cooking
#![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()
}


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

fn read_input() -> Vec<i32> {
    let _N: usize = read();
    let T = read_vec();
    T
}

fn initialize_dp(T: &Vec<i32>) -> Vec<bool> {
    let S = T.iter().sum::<i32>() as usize;
    let mut dp: Vec<bool> = vec![false; S+1];
    dp[0] = true;
    dp
}

fn update_dp(dp: Vec<bool>, t: i32) -> Vec<bool> {
    let mut new_dp = dp.to_vec();
    for (i, _) in dp.into_iter().enumerate().filter(|(_, b)| *b) {
        new_dp[i+(t as usize)] = true
    }
    new_dp
}

fn f(T: Vec<i32>) -> usize {
    let half = (T.iter().sum::<i32>() as usize + 1) / 2;
    let mut dp = initialize_dp(&T);
    for t in T.into_iter() {
        dp = update_dp(dp, t)
    }
    (half..dp.len()).filter(|&i| dp[i]).next().unwrap()
}

fn main() {
    let T = read_input();
    println!("{}", f(T))
}