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)) }