結果

問題 No.3424 Shooting Game
コンテスト
ユーザー atcoder8
提出日時 2026-01-11 18:51:17
言語 Rust
(1.92.0 + proconio + num)
結果
AC  
実行時間 139 ms / 2,000 ms
コード長 1,725 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 23,680 ms
コンパイル使用メモリ 414,680 KB
実行使用メモリ 24,200 KB
最終ジャッジ日時 2026-01-11 18:51:48
合計ジャッジ時間 26,117 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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::<Vec<_>>();
    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,
}
0