#pragma GCC optimize("Ofast","unroll-loops") //#pragma GCC push_options //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include #include #include using namespace::std; __attribute__((constructor))void init(){cin.tie(0);ios::sync_with_stdio(false);cout< #include #include #include templateusing pbds=__gnu_pbds::tree,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; templateusing pbds_map=__gnu_pbds::tree,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; templateusing hash_map=__gnu_pbds::gp_hash_table; templateusing pqueue =__gnu_pbds::priority_queue,__gnu_pbds::rc_binomial_heap_tag>; typedef long long lint; #define INF (1LL<<60) #define IINF (1<<30) #define EPS (1e-10) #define MOD 1000000007LL typedef vector vec; typedef vector> mat; typedef vector svec; typedef vector> smat; templateinline void numout(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<inline void numout2(T t){for(auto i:t)numout(i);} templateinline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<inline void output2(T t){for(auto i:t)output(i);} templateinline void _output(T t){bool f=0;for(lint i=0;iinline void _output2(T t){for(lint i=0;i=0;--i) #define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i) #define irep(i) for(lint i=0;;++i) #define all(n) begin(n),end(n) #define dist(a,b,c,d) sqrt(pow(a-c,2)+pow(b-d,2)) inline lint gcd(lint A,lint B){return B?gcd(B,A%B):A;} inline lint lcm(lint A,lint B){return A/gcd(A,B)*B;} inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;} inline bool chmax(auto& s,const auto& t){bool res=s dx={1,0,-1,0,1,1,-1,-1}; const vector dy={0,1,0,-1,1,-1,1,-1}; #define SUM(v) accumulate(all(v),0LL) auto call=[](auto f,auto... args){return f(f,args...);}; template struct dynamic_lazy_segment{ private: T et; E ee; lint n; lint size; struct node{ T val; E lazy; node *lch,*rch; node(dynamic_lazy_segment& seg):lch(nullptr),rch(nullptr){val=seg.et;lazy=seg.ee;} }; node* root; public: dynamic_lazy_segment(int size,T et,E ee):et(et),ee(ee),n(1),size(size){ while(nval; //全部区間内 if(a<=l&&r<=b){ t->lazy=g(t->lazy,x); eval(t,r-l,k); return h(t->val,t->lazy,r-l); } //一部区間内 if(!t->lch)t->lch=new node(*this); if(!t->rch)t->rch=new node(*this); return t->val=f(update(a,b,x,2*k+1,l,(l+r)/2,t->lch),update(a,b,x,2*k+2,(l+r)/2,r,t->rch)); } //0-indexed [a,b) T get(const lint& a,const lint& b,const lint& k,const lint& l,const lint& r,node* t){ eval(t,r-l,k); //区間外 if(r<=a||b<=l)return et; //全部区間内 if(a<=l&&r<=b)return t->val; //一部区間内 if(!t->lch)t->lch=new node(*this); if(!t->rch)t->rch=new node(*this); return f(get(a,b,2*k+1,l,(l+r)/2,t->lch),get(a,b,2*k+2,(l+r)/2,r,t->rch)); } inline void eval(node* t,const int& len,const int& k){ if(t->lazy==ee) return; if(k*2+1lch==nullptr)t->lch=new node(*this); if(t->rch==nullptr)t->rch=new node(*this); t->lch->lazy=g(t->lch->lazy,t->lazy); t->rch->lazy=g(t->rch->lazy,t->lazy); } t->val=h(t->val,t->lazy,len); t->lazy=ee; } T f(T a,T b){ return max(a,b); } T h(T a,E b,lint len){ return update(a,b); } E g(E a,E b){ return update(a,b); } auto update(auto a,auto b){return b==ee?a:b;} }; int main(){ lint n; cin>>n; vec a(n),b(n),c(n); rep(i,n)cin>>a[i]>>b[i]>>c[i]; vector>seg(n+10,dynamic_lazy_segment(-INF,-INF)); priority_queue,vector>,greater>>que; que.emplace(0,0,0); lint ans=0; while(!que.empty()){ lint day,money,like; tie(day,money,like)=que.top(); que.pop(); if(day==n){ if(money>=0)chmax(ans,like); continue; } if(seg[day+1].get(like,INF)