https://atcoder.jp/contests/typical90/tasks/typical90_k
単なるDPですが、よくあるパターンで終わりの日でソートします。
// Gravy Jobs #![allow(non_snake_case)] use std::cmp::max; //////////////////// 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() } //////////////////// Job //////////////////// #[derive(Clone, Eq, PartialEq)] struct Job(usize, usize, u64); impl Ord for Job { fn cmp(&self, other: &Self) -> std::cmp::Ordering { self.0.cmp(&other.0) } } impl PartialOrd for Job { fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> { Some(self.cmp(other)) } } impl Job { fn read() -> Job { let v: Vec<usize> = read_vec(); Job(v[0], v[1], v[2] as u64) } } //////////////////// process //////////////////// fn read_input() -> Vec<Job> { let N: usize = read(); let jobs: Vec<Job> = (0..N).map(|_| Job::read()).collect(); jobs } fn initialize_dp(jobs: &Vec<Job>) -> Vec<Option<u64>> { let T = jobs.iter().map(|job| job.0).max().unwrap(); let mut dp: Vec<Option<u64>> = vec![None; T+1]; dp[0] = Some(0); dp } fn update_dp(job: Job, dp: Vec<Option<u64>>) -> Vec<Option<u64>> { let mut new_dp: Vec<Option<u64>> = dp.to_vec(); if job.0 < job.1 { return new_dp } for t in 0..job.0-job.1+1 { let t1 = t + job.1; new_dp[t1] = match (dp[t], new_dp[t1]) { (Some(s), Some(s1)) => Some(max(s+job.2, s1)), (Some(s), None) => Some(s+job.2), (None, Some(s1)) => Some(s1), _ => None }; } new_dp } fn F(mut jobs: Vec<Job>) -> u64 { jobs.sort(); let mut dp = initialize_dp(&jobs); for job in jobs.into_iter() { dp = update_dp(job, dp) } dp.into_iter().filter_map(|n| n).max().unwrap() } fn main() { let jobs = read_input(); println!("{}", F(jobs)) }