結果
問題 | No.1826 Fruits Collecting |
ユーザー |
![]() |
提出日時 | 2023-10-26 14:06:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 229 ms / 2,000 ms |
コード長 | 1,248 bytes |
コンパイル時間 | 3,467 ms |
コンパイル使用メモリ | 262,688 KB |
実行使用メモリ | 23,492 KB |
最終ジャッジ日時 | 2024-09-25 12:23:37 |
合計ジャッジ時間 | 11,881 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;#include<atcoder/segtree>ll op(ll a,ll b){return max(a,b);}ll e(){return -1e18;}int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int n;cin>>n;vector<ll> dx;vector<ll> t(n),x(n),v(n);for(int i = 0;i<n;i++){cin>>t[i]>>x[i]>>v[i];dx.push_back(t[i]-x[i]);dx.push_back(x[i]+t[i]);}dx.push_back(0);vector<int> idx(n);for(int i = 0;i<n;i++) idx[i] = i;sort(dx.begin(),dx.end());dx.erase(unique(dx.begin(),dx.end()),dx.end());sort(idx.begin(),idx.end(),[&](int i,int j){if(t[i]+x[i]==t[j]+x[j]) return t[i] - x[i] < t[j] - x[j];return t[i] + x[i] < t[j] + x[j];});ll ans = 0;int m = dx.size();atcoder::segtree<ll,op,e> seg(m);int nk = lower_bound(dx.begin(),dx.end(),0) - dx.begin();for(int i = 0;i<n;i++){int ni = idx[i];int nni = lower_bound(dx.begin(),dx.end(),t[ni]-x[ni]) - dx.begin();ll now = seg.prod(0,nni+1) + v[ni];if(-t[ni]<=x[ni]&&x[ni]<=t[ni]) now = op(now,v[ni]);seg.set(nni,op(seg.get(nni),now));ans = max(ans,now);}cout<<ans<<endl;}