Submission #859993

#TimeUsernameProblemLanguageResultExecution timeMemory
859993jk410Salesman (IOI09_salesman)C++17
60 / 100
656 ms30804 KiB
#include <iostream> #include <algorithm> #define maxx(a,b) a=max(a,b) using namespace std; typedef long long ll; struct market{ int t,l,m; void input(){ cin>>t>>l>>m; } }; const ll INF=(int)1e18; const int MAX=500001; ll update(ll *tree,int x,ll v,int l,int r,int n){ if (r<x||x<l) return tree[n]; if (l==r) return maxx(tree[n],v); int m=(l+r)>>1; return tree[n]=max(update(tree,x,v,l,m,n<<1),update(tree,x,v,m+1,r,n<<1|1)); } ll query(ll *tree,int lx,int rx,int l,int r,int n){ if (r<lx||rx<l) return -INF; if (lx<=l&&r<=rx) return tree[n]; int m=(l+r)>>1; return max(query(tree,lx,rx,l,m,n<<1),query(tree,lx,rx,m+1,r,n<<1|1)); } int N,U,D,S; market A[500001]; ll TreeU[1<<20],TreeD[1<<20]; ll DPU[500001],DPD[500001]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); fill(TreeU+1,TreeU+(1<<20),-INF); fill(TreeD+1,TreeD+(1<<20),-INF); cin>>N>>U>>D>>S; for (int i=0; i<N; i++) A[i].input(); A[N]={MAX,S,0}; sort(A,A+N+1,[&](market a,market b)->bool{ if (a.t!=b.t) return a.t<b.t; return a.l<b.l; }); update(TreeU,S,-(ll)U*S,1,MAX,1); update(TreeD,S,(ll)D*S,1,MAX,1); for (int r=0,l=0; r<=N; r++){ if (r==N||A[r+1].t!=A[r].t){ for (int i=r; i>=l; i--){ DPU[i]=-INF; ll umx=query(TreeU,A[i].l,MAX,1,MAX,1); if (umx!=-INF) { DPU[i]=umx+A[i].m+(ll)U*A[i].l; update(TreeU,A[i].l,DPU[i]-(ll)U*A[i].l,1,MAX,1); } } for (int i=l; i<=r; i++){ DPD[i]=-INF; ll dmx=query(TreeD,1,A[i].l,1,MAX,1); if (dmx!=-INF){ DPD[i]=dmx+A[i].m-(ll)D*A[i].l; update(TreeD,A[i].l,DPD[i]+(ll)D*A[i].l,1,MAX,1); } } for (int i=l; i<=r; i++){ update(TreeD,A[i].l,max(DPU[i],DPD[i])+(ll)D*A[i].l,1,MAX,1); update(TreeU,A[i].l,max(DPU[i],DPD[i])-(ll)U*A[i].l,1,MAX,1); } l=r+1; } } /* for (int i=0; i<=N; i++){ DP[i]=-INF; ll umx=query(TreeU,A[i].l,MAX,1,MAX,1); if (umx!=-INF) maxx(DP[i],umx+A[i].m+(ll)U*A[i].l); ll dmx=query(TreeD,1,A[i].l,1,MAX,1); if (dmx!=-INF) maxx(DP[i],dmx+A[i].m-(ll)D*A[i].l); update(TreeU,A[i].l,DP[i]-(ll)U*A[i].l,1,MAX,1); update(TreeD,A[i].l,DP[i]+(ll)D*A[i].l,1,MAX,1); } cout<<DP[N]; */ cout<<max(DPU[N],DPD[N]); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...