結果
問題 | No.2808 Concentration |
ユーザー |
|
提出日時 | 2024-07-09 22:37:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 449 ms / 2,000 ms |
コード長 | 2,038 bytes |
コンパイル時間 | 2,834 ms |
コンパイル使用メモリ | 215,704 KB |
最終ジャッジ日時 | 2025-02-22 02:42:12 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 57 |
ソースコード
#include <bits/stdc++.h> #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; using ll = long long; const ll mod = 998244353; #define fi first #define se second #define rep(i,n) for(ll i=0;i<n;i++) #define all(x) x.begin(),x.end() #define faster ios::sync_with_stdio(false);cin.tie(nullptr) template<typename T> struct RMQ{ const T INF=-1LL<<60; ll N; vector<T> dat; RMQ(ll N_):N(),dat(N_*4,INF){ ll x=1; while(N_>x) x*=2; N=x; } void update(ll i,T x){ i+=N-1; dat[i]=max(dat[i],x); while(i>0){ i=(i-1)/2; dat[i]=max(dat[i*2+1],dat[i*2+2]); } } T query(ll a,ll b){return query_sub(a,b,0,0,N);} T query_sub(ll a,ll b,ll k,ll l,ll r){ if(r<=a||b<=l){ return INF; }else if(a<=l&&r<=b){ return dat[k]; }else{ T vl=query_sub(a,b,k*2+1,l,(l+r)/2); T vr=query_sub(a,b,k*2+2,(l+r)/2,r); return max(vl,vr); } } }; int main() { ll N,S,H; cin >> N >> S >> H; vector<ll> X(N),Y(N),Z(N); rep(i,N){ cin >> X[i] >> Y[i] >> Z[i]; } vector<ll> sum(N+1,0); rep(i,N) sum[i+1]=sum[i]+Z[i]; RMQ<ll> dp1(N),dp2(N),dp3(N); rep(i,N){ dp1.update(i,0); dp2.update(i,0); if(Y[i]-X[i]<=S){ dp1.update(i,Z[i]); dp2.update(i,Z[i]); } dp3.update(i,dp1.query(i,i+1)-sum[i+1]); } rep(i,N){ if(Y[i]-X[i]<=S){ ll k=upper_bound(all(Y),X[i]-H)-Y.begin(); if(k>0){ ll x=dp2.query(0,k); dp1.update(i,x+Z[i]); dp2.update(i,x+Z[i]); dp3.update(i,x+Z[i]-sum[i+1]); } } ll k=lower_bound(all(X),Y[i]-S)-X.begin(); if(k<i){ ll x=dp3.query(k,i)+sum[i+1]; dp2.update(i,x); } } cout << dp2.query(0,N) << endl; return 0; }