use proconio::{fastout, input}; #[fastout] fn main() { input! { n: usize, t: u32, targets: [(u32, u32, u32); n], } println!("{}", output(solve(t, targets))); } fn solve(t: u32, mut targets: Vec<(u32, u32, u32)>) -> u64 { let mut dp = [0; 200_002]; let mut pq = std::collections::BinaryHeap::with_capacity(targets.len()); targets.sort_unstable_by_key(|&(l, _, _)| l); let mut targets = targets.into_iter().peekable(); for time in 0..=200_000 { while let Some(&(l, r, p)) = targets.peek() { if l == time { targets.next(); pq.push((p, r)); } } while let Some(&(_, r)) = pq.peek() { if time > r { pq.pop(); } } let p = pq.peek().unwrap_or(&(0, u32::MAX)).0; dp[(time + 1) as usize] = dp[time as usize].max(dp[time.saturating_sub(t - 1) as usize] + p as u64); } dp[200_001] } fn output(ans: u64) -> u64 { ans }