結果
問題 |
No.2808 Concentration
|
ユーザー |
|
提出日時 | 2024-07-27 04:09:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 218 ms / 2,000 ms |
コード長 | 1,151 bytes |
コンパイル時間 | 4,726 ms |
コンパイル使用メモリ | 253,536 KB |
最終ジャッジ日時 | 2025-02-23 19:02:42 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 57 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using ll = long long; #define rep(i, s, t) for (ll i = s; i < (ll)(t); i++) template<typename T> bool chmin(T &x, T y) { return x > y ? (x = y, true) : false; } template<typename T> bool chmax(T &x, T y) { return x < y ? (x = y, true) : false; } struct io_setup { io_setup() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(15); } } io_setup; // template atcoder segtree using S = ll; S op(S a, S b){ return max(a, b); } S e(){ return -1e18; } using segtree = atcoder::segtree<S,op,e>; int main(){ ll n,s,h; cin>>n>>s>>h; vector<ll> x(n),y(n),z(n); rep(i,0,n) cin>>x.at(i)>>y.at(i)>>z.at(i); vector<ll> sz(n+1); rep(i,0,n) sz.at(i+1)=sz.at(i)+z.at(i); segtree dp1(n+1),dp2(n+1); rep(i,0,n){ if(y.at(i)-x.at(i)>s) continue; int mny=upper_bound(y.begin(),y.end(),x.at(i)-h)-y.begin(); int mxx=lower_bound(x.begin(),x.end(),y.at(i)-s)-x.begin(); dp1.set(i,max(0LL,dp2.prod(0,mny))-sz.at(i)); if(mxx<i+1) dp2.set(i,dp1.prod(mxx,i+1)+sz.at(i+1)); else dp2.set(i,sz.at(i+1)); } cout<<max(0LL,dp2.all_prod())<<endl; }