K4PC : D - たのしい運動会(School Sports is Fun)

ライブラリのグダグダがなかった分、Cよりこちらの方が楽だった。
http://k4pc.contest.atcoder.jp/tasks/k4pc_d

問題

運動会においてN個の競技がある。
各競技はA[i]～B[i]の時間にわたり開催され、参加すると満足度F[i]を得る。
時間の重複する競技への多重参加や、１競技に部分的に参加することはできない。

なお、運動会に参加している間、競技参加の有無を問わず時間1につき満足度がC減少する。
運動会には任意のタイミングで参加・退場可能だが、１回退場すると再参加はできない。

運動会の参加タイミングと、参加する競技を最適化したとき、得られる最大の満足度を答えよ。

解法

競技を終了時刻B[i]順にソートし、処理していく。

これまでの競技における(競技の終了時刻, そこまでの合計満足度)を配列にしまい管理する。
各競技に参加した場合、配列中からA[i]以前で最もA[i]に近い(競技の終了時刻, そこまでの合計満足度)をlower_bound等で求め、そこまでの満足度に(F[i] - C*(B[i]-前の競技の終了時刻))を足したものがこの競技終了時の最大満足度である。
よって(B[i], そこまでの満足度 + F[i] - C*(B[i]-前の競技の終了時刻))を配列に足していく。

終了時刻順に処理するので、配列の中身における時刻は昇順になる。
その際、最大満足度を得るのに最適でない競技があればそれを外しておく。
例えば配列中に(tx, sx)、(ty, sy)という２要素があるとする。
tx＜tyとすると、sy ＜ sx - C*(ty-tx)だったら、tyに終わる競技に参加する意味はないので、配列から外す。

ll N,C;
ll A[100020],B[100020],F[100020];
pair<ll,int> P[1000050];

ll ma=0;
vector<pair<ll,ll> > V;

void solve() {
	int i,j,k,l,r,y; string s;
	
	cin>>N>>C;
	FOR(i,N) {
		cin>>A[i]>>B[i]>>F[i];
		P[i]=make_pair(B[i],i);
	}
	V.push_back(make_pair(0,0));
	
	sort(P,P+N);
	FOR(j,N) {
		i=P[j].second;
		ll x=F[i]-C*(B[i]-A[i]); // first
		vector<pair<ll,ll> >::iterator it=lower_bound(V.begin(),V.end(),make_pair(A[i]+1,0LL));
		it--;
		x=max(x,it->second + F[i] - C*(B[i]-it->first));
		while(V.size() && V.back().first==B[i] && V.back().second<x) V.pop_back();
		int ng=0;
		if(V.size() && V.back().second-C*(B[i]-V.back().first)>=x) ng=1;
		if(ng==0) V.push_back(make_pair(B[i],x));
		ma=max(ma,x);
	}
	cout<<ma<<endl;
	
}

まとめ

最適手のリストをキュー風に管理する問題、しばしば出るね。