Codeforces #386 Div2 F. Music in Car

3000ptが2問で驚愕していたが、普段なら2000ptぐらい。
http://codeforces.com/contest/746/problem/F

問題

N個の曲があり、それぞれ楽しさはA[i]、かかる時間はT[i]である。
これらのうち、時間Kの間で連続するいくつかの曲を聴きたい。
この際、最大W曲までは半分だけ聞いて次の曲に行くことができる(楽しさは同じくA[i]得られる)。
得られる楽しさの総和の最大値を求めよ。

解法

尺取り法の要領で、先頭の曲に対し時間K内に聞ける末尾の曲を求めていく。
setやpriority_queueを使い、かかる時間上位W曲を半分だけ聞く対象にしながら処理をしていくとよい。

int N,W,K;
ll A[202020];
ll T[202020];
ll SA[202020];
int type[202020];
set<pair<int,int>> H,F;
ll TT;

void add(int id) {
	type[id]=1;
	TT+=(T[id]+1)/2;
	H.insert({T[id],id});
	
	if(H.size()>W) {
		auto h=*H.begin();
		H.erase(h);
		TT-=(h.first+1)/2;
		
		type[h.second]=0;
		TT+=h.first;
		F.insert(h);
	}
	
}

void del(int id) {
	if(type[id]==0) {
		TT-=T[id];
		F.erase({T[id],id});
	}
	else {
		TT-=(T[id]+1)/2;
		H.erase({T[id],id});
		if(F.size()) {
			auto f=*F.rbegin();
			F.erase(f);
			TT-=f.first;
			type[f.second]=1;
			TT+=(f.first+1)/2;
			H.insert(f);
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>W>>K;
	FOR(i,N) {
		cin>>A[i];
		SA[i+1]=SA[i]+A[i];
	}
	FOR(i,N) cin>>T[i];
	ll ma=0;
	int L,R=0;
	
	FOR(L,N) {
		while(R<N) {
			add(R);
			if(TT>K) {
				del(R);
				break;
			}
			R++;
		}
		ma=max(ma,SA[R]-SA[L]);
		del(L);
	}
	cout<<ma<<endl;
}

まとめ

ずいぶん不自然な問題設定だな…。