結果
問題 | No.2808 Concentration |
ユーザー |
|
提出日時 | 2024-07-09 22:02:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,785 bytes |
コンパイル時間 | 2,360 ms |
コンパイル使用メモリ | 209,304 KB |
最終ジャッジ日時 | 2025-02-22 02:41:23 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 5 WA * 52 |
ソースコード
#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=0;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];}RMQ<ll> dp1(N),dp2(N);rep(i,N) if(Y[i]-X[i]<=S){dp1.update(i,Z[i]);dp2.update(i,Z[i]);}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]);}}ll k=lower_bound(all(X),Y[i]-S)-X.begin();if(k<i){ll x=dp1.query(k,i);dp2.update(i,x+Z[i]);}}cout << dp2.query(0,N) << endl;return 0;}