結果

問題 No.3424 Shooting Game
コンテスト
ユーザー tnakao0123
提出日時 2026-01-11 18:51:35
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 246 ms / 2,000 ms
コード長 1,096 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 736 ms
コンパイル使用メモリ 93,760 KB
実行使用メモリ 25,084 KB
最終ジャッジ日時 2026-01-11 18:51:38
合計ジャッジ時間 3,278 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/* -*- coding: utf-8 -*-
 *
 * 3424.cc:  No.3424 Shooting Game - yukicoder
 */

#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
#include<functional>

using namespace std;

/* constant */

const int MAX_N = 200000;
const int MAX_R = 200000 + 2;

/* typedef */

using ll = long long;
using vi = vector<int>;
using msig = multiset<int,greater<int>>;

/* global variables */

vi lps[MAX_R], rps[MAX_R];
ll dp[MAX_R];

/* subroutines */

void setmax(ll &a, ll b) { if (a < b) a = b; }

/* main */

int main() {
  int n, t;
  scanf("%d%d", &n, &t);

  int maxr = 0;
  for (int i = 0; i < n; i++) {
    int l, r, p;
    scanf("%d%d%d", &l, &r, &p);
    lps[l].push_back(p);
    rps[r].push_back(p);
    maxr = max(maxr, r);
  }

  msig ps;
  fill(dp, dp + maxr + 2, -1);
  dp[0] = 0;
  for (int i = 0; i <= maxr; i++) {
    setmax(dp[i + 1], dp[i]);

    for (auto p: lps[i]) ps.insert(p);

    if (! ps.empty())
      setmax(dp[min(maxr + 1, i + t)], dp[i] + *ps.begin());
    
    for (auto p: rps[i]) ps.erase(ps.find(p));
  }

  printf("%lld\n", dp[maxr + 1]);
  
  return 0;
}
0