Submission #13390

#TimeUsernameProblemLanguageResultExecution timeMemory
13390ggoh코알라 (JOI13_koala)C++98
100 / 100
155 ms77680 KiB
#include<cstdio> #include<vector> using namespace std; struct Node{ int s,e;long long v;int left,right; }; vector<Node>Tree; long long INF=-1e18,x,y,A,X[100005],E[100005]; int T[100005],i,B[100005],m,Y[100005],k,D,N; void update(int num,int pos,long long val) { Node t=Tree[num]; if(t.v<val) { Tree[num].v=val; } long long h=(t.s+t.e-1)/2; if(t.s==t.e-1) { return ; } if(h+1>pos) { if(t.left==-1) { Tree.push_back({t.s,h+1,INF,-1,-1}); Tree[num].left=Tree.size()-1; } update(Tree[num].left,pos,val); } else { if(t.right==-1) { Tree.push_back({h+1,t.e,INF,-1,-1}); Tree[num].right=Tree.size()-1; } update(Tree[num].right,pos,val); } } long long rmq(int num,int p,int q) { Node t=Tree[num]; if(t.e<p||q<t.s)return INF; if(t.s>=p&&t.e<=q)return t.v; long long res=INF; if(t.left>=0)res=max(res,rmq(t.left,p,q)); if(t.right>=0)res=max(res,rmq(t.right,p,q)); return res; } main() { scanf("%d%d%d%lld%d",&k,&m,&D,&A,&N); for(i=1;i<=N;i++) { scanf("%d%d",&T[i],&B[i]); T[i]-=k; X[i]=T[i]/D; Y[i]=T[i]%D; } T[N+1]=m-k; X[N+1]=T[N+1]/D; Y[N+1]=T[N+1]%D; B[0]=B[N+1]=0; Tree.push_back({0,D,INF,-1,-1}); E[0]=0; update(0,Y[0],X[0]*A); for(i=1;i<=N+1;i++) { x=rmq(0,0,Y[i]); y=rmq(0,Y[i],D); E[i]=max(x-A,y)-X[i]*A+B[i]; update(0,Y[i],E[i]+X[i]*A); } printf("%lld",E[N+1]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...