競プロ典型 011

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