結果
問題 | No.1826 Fruits Collecting |
ユーザー |
![]() |
提出日時 | 2022-01-28 22:43:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 378 ms / 2,000 ms |
コード長 | 1,034 bytes |
コンパイル時間 | 4,669 ms |
コンパイル使用メモリ | 262,336 KB |
最終ジャッジ日時 | 2025-01-27 17:08:37 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) #define Inf 1000000000000000001; long long op(long long a,long long b){ return max(a,b); } long long e(){ return -Inf; } int main(){ int n; cin>>n; vector<array<long long,3>> a(n); rep(i,n){ long long t,x,v; cin>>t>>x>>v; a[i][0] = t+x; a[i][1] = t-x; a[i][2] = v; } sort(a.begin(),a.end()); vector<long long> t; rep(i,n)t.push_back(a[i][1]); t.push_back(0); sort(t.begin(),t.end()); t.erase(unique(t.begin(),t.end()),t.end()); segtree<long long,op,e> seg(t.size()); { int d = distance(t.begin(),lower_bound(t.begin(),t.end(),0LL)); seg.set(d,0); } bool f = false; rep(i,n){ if(a[i][0]<0||a[i][1]<0)continue; int d = distance(t.begin(),lower_bound(t.begin(),t.end(),a[i][1])); long long v = seg.prod(0,d+1); v += a[i][2]; seg.set(d,max(v,seg.get(d))); } cout<<seg.all_prod()<<endl; return 0; }