Codeforces #687 Div1 C. New Game Plus!

これも本番割とすんなり。
https://codeforces.com/contest/1456/problem/C

問題

N体のモンスターがおり、それぞれパラメータが与えられる。パラメータは負の値もあり得る。
これからこのモンスターを任意の順で1匹ずつ倒すことを考える。
ここで、主人公には二つのパラメータがある。いずれも初期状態では0である。

• ボーナス
• スコア

モンスターを倒すと、現在のボーナス分だけスコアに加算されたのち、倒したパラメータがボーナスに加算される。
ここで、途中K回だけボーナス値を0リセットできるとする。
得られる最大スコアを求めよ。

解法

パラメータが正のモンスターは、連続して倒すのがお得。
そこで、まず最初にその部分を処理しよう。
パラメータの大きい順に、ボーナスが正である範囲で連続して敵を倒していく。

そうすると、残るのはパラメータが負のモンスターである。
リセットしないでいると、パラメータの負の分が累積する。
そこでそれらを(K+1)個のグループに分け、グループ処理毎にリセットしよう。

int N,K;
ll C[505050];
vector<int> T[515151];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>C[i];
	sort(C,C+N);
	ll cur=0;
	ll sum=0;
	while(N) {
		if(cur+C[N-1]<0) break;
		sum+=cur;
		cur+=C[N-1];
		N--;
	}
	x=0;
	while(N) {
		T[x%(K+1)].push_back(C[N-1]);
		x++;
		N--;
	}
	
	FOR(i,K+1) {
		FORR(t,T[i]) {
			sum+=cur;
			cur+=t;
		}
		cur=0;
	}
	cout<<sum<<endl;
	
}

まとめ

Div1 Cの割には簡単。これ1250ptでもいいんじゃないかな。