Codeforces #523 Div2 D. TV Shows

Dでしょうもないミスをした…。
http://codeforces.com/contest/1061/problem/D

問題

N個のテレビ番組があり、各番組iの放映時間は[L[i], R[i]]である。
全番組を漏らさず見るよう、いくつかのテレビで番組を見る。
各テレビは同時に1つの番組を見ることしかできない。
また、番組の途中でその番組を見るテレビを変更することができない。

テレビを期間[L,R]の間借りる場合、間に番組を見ない場合でも定数X,Yに対しX+(R-L)*Yのコストがかかる。
全番組を見る最小コストを答えよ。

解法

multiset等ですでに借りたテレビ群のうち、利用される最初の時刻を管理しよう。
後は番組をR[i]の降順に処理する。

multiset内に、今見ている番組の後に使い始めるテレビがある場合、そのテレビの流用を考えよう。
その場合、テレビを使い回す方がコストが低い場合、使いまわす。そうでなければ新規に借りる。

int N;
ll X,Y;
int L[101010],R[101010];
ll mo=1000000007;
multiset<ll> M;
vector<pair<int,int>> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>Y;
	ll ret=0;
	FOR(i,N) {
		cin>>L[i]>>R[i];
		V.push_back({R[i],L[i]});
	}
	
	sort(ALL(V));
	reverse(ALL(V));
	FORR(v,V) {
		ll R=v.first;
		ll L=v.second;
		auto it=M.lower_bound(R+1);
		
		if(it!=M.end() && (*it-L)*Y<X+(R-L)*Y) {
			(ret+=(*it-L)*Y)%=mo;
			M.erase(it);
		}
		else {
			(ret+=X+(R-L)*Y)%=mo;
		}
		M.insert(L);
	}
	cout<<ret<<endl;
	
}

まとめ

せっかく1位になるチャンスだったのにもったいない。