85B Embassy Queue

問題

大使館にn人の人がやってくる。i番目の人がくる時刻はc[i]である。
大使館では3つの手続きを、決まった順に行う必要がある。

1番目の手続きにはt1の時間がかかり、窓口はk1個ある。
2番目の手続きにはt2の時間がかかり、窓口はk2個ある。
3番目の手続きにはt3の時間がかかり、窓口はk3個ある。

手続き以外にかかる時間を0とするとき、最も時間がかかる人が手続きを終えるまでにかかる時間を求めよ。

制約条件

k1,k2,k3≦10^9
t1,t2,t3≦10^5
n≦10^5
c[i]≦10^9

方針

それぞれの手続きにおいて、完了する時刻をシミュレートによって求める。
このシミュレートは、queueを使い、

• k人手続き中のときは、時間を進める
• k人未満が手続き中のときは早い人に手続きをさせる

操作を愚直にやればよい。

ソースコード

ll n,c[100000],A[100000],B[100000],C[100000];
ll q[100000];

void solve(ll *a,ll *r,ll k,ll t){
	ll tm=0,hd=0,tl=0,s=0;
	rep(i,n){
		while(hd<tl&&tm>=q[hd])r[s++]=q[hd++];
		if(tl-hd<k)q[tl++]=max(tm,a[i])+t;
		else tm=q[hd], i--;
	}
	while(hd<tl)r[s++]=q[hd++];
}

void run(){
	ll k1,k2,k3,t1,t2,t3;
	
	cin>>k1>>k2>>k3;
	cin>>t1>>t2>>t3;
	cin>>n;
	
	rep(i,n)cin>>c[i];
	solve(c,A,k1,t1);
	solve(A,B,k2,t2);
	solve(B,C,k3,t3);
	
	ll ans=0; rep(i,n)ans=max(ans,C[i]-c[i]);
	cout<<ans<<endl;
}