제출 #1020448

#제출 시각아이디문제언어결과실행 시간메모리
1020448boyliguanhanSalesman (IOI09_salesman)C++17
100 / 100
1047 ms65536 KiB
#include<bits/stdc++.h> using namespace std; int U,D; #define N 500100 struct fenwicktree{ int active=0; int T[N]; vector<pair<int,int>>done; void upd(int n,int v){ for(;n<N;n+=n&-n) done.push_back({n,T[n]}),T[n]=max(T[n],v); } int query(int n){ int ans=-1e9; while(n) ans=max(ans,T[n]),n-=n&-n; return ans; } void tog(){ if(active) { reverse(done.begin(),done.end()); for(auto[x,v]:done) T[x]=v; } active^=1; done.clear(); } fenwicktree(){for(auto&i:T)i=-2e9;} } up,dn; void dostuf(int pos,int v){ up.upd(pos,v+pos*D); dn.upd(N-pos,v-pos*U); } int getans(int pos){ return max(up.query(pos)-pos*D, dn.query(N-pos)+pos*U); } void tog(){ up.tog(),dn.tog(); } map<int,vector<pair<int,int>>>stuff; int bst[N]; int main(){ int n,p; cin>>n>>U>>D>>p; for(int i=1;i<=n;i++){ int t,l,m; cin>>t>>l>>m; stuff[t].push_back({l,m}); } dostuf(p,0); for(auto[day,kirby]:stuff){ tog(); sort(kirby.begin(),kirby.end()); for(auto[x,y]:kirby) dostuf(x,bst[x]=getans(x)+y); tog(); tog(); reverse(kirby.begin(),kirby.end()); for(auto[x,y]:kirby) bst[x]=max(bst[x],getans(x)+y), dostuf(x,getans(x)+y); tog(); for(auto[x,y]:kirby) dostuf(x,bst[x]); } cout<<getans(p); }
#Verdict Execution timeMemoryGrader output
Fetching results...