use std::collections::BTreeSet; use proconio::input; fn main() { input! { (n, t): (usize, usize), lrp: [(usize, usize, usize); n], } let mut events = lrp .iter() .enumerate() .flat_map(|(i, &(l, r, p))| { [ Event { id: i, enter: true, time: l, point: p, }, Event { id: i, enter: false, time: r + 1, point: p, }, ] }) .collect::>(); events.sort_unstable_by_key(|event| event.time); let max_event_time = events.iter().map(|event| event.time).max().unwrap(); let mut points = vec![0; max_event_time + 1]; let mut prev_time = 0; let mut target_points = BTreeSet::new(); for &event in &events { let max_target_point = target_points .iter() .next_back() .map_or(0, |&(point, _)| point); points[prev_time..event.time].fill(max_target_point); if event.enter { target_points.insert((event.point, event.id)); } else { target_points.remove(&(event.point, event.id)); } prev_time = event.time; } let mut dp = vec![0_usize; max_event_time + t + 1]; for i in 0..=max_event_time { dp[i + t] = dp[i + t].max(dp[i + t - 1]).max(dp[i] + points[i]); } let max_total_point = *dp.iter().max().unwrap(); println!("{max_total_point}"); } #[derive(Debug, Clone, Copy)] struct Event { id: usize, enter: bool, time: usize, point: usize, }