結果
問題 | 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;}