yukicoder : No.2957 Combo Deck Builder

こちらもコードは短め。
https://yukicoder.me/problems/no/2957

問題

N個のカードがある。
カードiにはそれぞれパラメータC[i],X[i],Y[i]が振られている。
カードを使うとき、すでにC[i]枚以上カードを使っていたらX[i]、そうでなければY[i]のダメージを与えることができる。

任意の順でカードを使うとき、総ダメージの最大値を求めよ。

解法

X[i],Y[i]はいずれも正なので、カードは全部使い切るのが良い。
まずmin(X[i],Y[i])は必ず与えられるので、その分は解に計上しよう。
あとはX[i]＞Y[i]であるカードと、X[i]＜Y[i]であるカードそれぞれ考える。

とはいえこれは区間スケジューリングの応用で、X[i]＞Y[i]である場合、1枚目から見て使用可能なカードのうちX[i]-Y[i]が最大のものを貪欲に使えばよい。
同様に、X[i]＜Y[i]であるカードは、N枚目からさかのぼって行って、Y[i]-X[i]が最大のものを貪欲に使えばよい。

int N;
int C[202020],X[202020],Y[202020];
vector<int> addf[202020];
vector<int> addb[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	ll ret=0;

	cin>>N;
	FOR(i,N) {
		cin>>C[i]>>X[i]>>Y[i];
		ret+=min(X[i],Y[i]);
		
		if(X[i]>Y[i]) {
			addf[C[i]+1].push_back(X[i]-Y[i]);
		}
		if(X[i]<Y[i]) {
			addb[C[i]].push_back(Y[i]-X[i]);
		}
	}
	priority_queue<int> Q;
	for(i=1;i<=N;i++) {
		FORR(a,addf[i]) Q.push(a);
		if(Q.size()) {
			ret+=Q.top();
			Q.pop();
		}
	}
	while(Q.size()) Q.pop();
	
	for(i=N;i>=1;i--) {
		FORR(a,addb[i]) Q.push(a);
		if(Q.size()) {
			ret+=Q.top();
			Q.pop();
		}
	}
	cout<<ret<<endl;
	
}

まとめ

そういや最近のyukicoderはアルファベットの問題名多いな。