AtCoder Beginner Contest 375 E

https://atcoder.jp/contests/abc375/tasks/abc375_e

DPです。状態を各チームの強さ、値を変更人数とします。各チームの強さの最大は500ですが、2チーム分だけを状態とすればよいです。

// 3 Team Division
#![allow(non_snake_case)]

use std::cmp::min;


//////////////////// 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<(usize, usize)> {
    let N: usize = read();
    let persons: Vec<(usize, usize)> = (0..N).map(|_| read_vec::<usize>()).
                                              map(|v| (v[0] - 1, v[1])).
                                              collect();
    persons
}

type DP = Vec<Vec<i32>>;

fn update_DP(p: (usize, usize), dp: DP) -> DP {
    let update = |x: i32, y: i32| -> i32 {
        if x == -1 { y } else { min(x, y) }
    };
    
    let (A, B) = p;
    let S = dp.len();
    let mut new_dp: DP = vec![vec![-1; S+1]; S+1];
    for x in 0..S {
        for y in 0..S {
            if dp[x][y] == -1 {
                continue
            }
            if x + B < S + 1 {
                let change1: i32 = if A == 0 { 0 } else { 1 };
                new_dp[x+B][y] = update(new_dp[x+B][y], dp[x][y] + change1);
            }
            if y + B < S + 1 {
                let change2: i32 = if A == 1 { 0 } else { 1 };
                new_dp[x][y+B] = update(new_dp[x][y+B], dp[x][y] + change2);
            }
            let change3: i32 = if A == 2 { 0 } else { 1 };
            new_dp[x][y] = update(new_dp[x][y], dp[x][y] + change3)
        }
    }
    new_dp
}

fn F(persons: Vec<(usize, usize)>) -> i32 {
    let sum_B = persons.iter().map(|&(_, B)| B).sum::<usize>();
    if sum_B % 3 != 0 {
        return -1
    }
    
    let S = sum_B / 3;
    let mut dp: DP = vec![vec![-1; S+1]; S+1];
    dp[0][0] = 0;
    for p in persons.into_iter() {
        dp = update_DP(p, dp)
    }
    
    dp[S][S]
}

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