Codeforces Round #386 (Div. 2), problem: (F) Music in Car Solution in C/C++
#include <stdio.h> #include <string.h> #define MAX(X,Y) ((X)>(Y) ? (X) : (Y)) int n,w,k,a[200010],t[200010],sz[2],heap[2][200010],ind[200010],pos[200010]; void push(int k,int opt); int pop(int opt); void del(int u,int opt); void up(int u,int opt); void down(int u,int opt); int cmp(int u,int v,int opt); void swap(int u,int v,int opt); int main(void) { //freopen("music.in","r",stdin); //freopen("music.out","w",stdout); scanf("%d%d%d",&n,&w,&k); int i; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n;i++) scanf("%d",&t[i]); sz[0]=sz[1]=0; memset(pos,-1,sizeof(pos)); int l=1,s=0,st=0,ans=0,p; for(sz[0]=sz[1]=0,i=1;i<=n;i++) { push(i,0); s+=a[i]; st+=(t[i]+1)/2; if(sz[0]>w) { p=pop(0); st-=(t[p]+1)/2; push(p,1); st+=t[p]; } while(st>k) { if(pos[l]) { del(ind[l],1); s-=a[l]; st-=t[l]; } else { del(ind[l],0); s-=a[l]; st-=(t[l]+1)/2; if(sz[1]) { p=pop(1); st-=t[p]; push(p,0); st+=(t[p]+1)/2; } } l++; } ans=MAX(ans,s); } printf("%d\n",ans); return 0; } void push(int k,int opt) { heap[opt][++sz[opt]]=k; pos[k]=opt; ind[k]=sz[opt]; up(sz[opt],opt); } int pop(int opt) { int ans=heap[opt][1]; swap(1,sz[opt],opt); sz[opt]--; down(1,opt); return ans; } void del(int u,int opt) { swap(u,sz[opt],opt); sz[opt]--; if( u>1 && cmp(u,u/2,opt)<0 ) up(u,opt); else down(u,opt); } void up(int u,int opt) { if( u>1 && cmp(u,u/2,opt)<0 ) { swap(u,u/2,opt); up(u/2,opt); } } void down(int u,int opt) { if(u*2>sz[opt]) return; int v=u*2; if( v+1<=sz[opt] && cmp(v+1,v,opt)<0 ) v++; if(cmp(v,u,opt)<0) { swap(u,v,opt); down(v,opt); } } int cmp(int u,int v,int opt) { int ans; if(t[heap[opt][u]]<t[heap[opt][v]]) ans=-1; else if(t[heap[opt][u]]>t[heap[opt][v]]) ans=1; else ans=0; if(opt) ans*=-1; return ans; } void swap(int u,int v,int opt) { int t1,t2; t1=heap[opt][u]; t2=heap[opt][v]; heap[opt][u]=t2; heap[opt][v]=t1; ind[t2]=u; ind[t1]=v; }
