Codeforces #664 Div1 A. Boboniu Chats with Du

ダメダメだった回の後にだいぶ復旧した回。
https://codeforces.com/contest/1394/problem/A

問題

N要素の数列Aが与えられる。
これを並べ替えたうち、いくつかの要素を選び、その和を最大化したい。
ただし、途中Mを超える値を選ぶ場合、その後D要素は選べない。

最大値を求めよ。

解法

Mを超える値を選ぶ数nを総当たりしよう。
そのためには、(n-1)*D個選ばない値を埋めなくてはならない。

Mを超える値のうち残り分を極力選び、あとはM以下の値のうち小さい順に埋めて行くケースを考えよう。

int N,D;
ll M;
vector<ll> A,B,AS,BS;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>D>>M;
	FOR(i,N) {
		cin>>x;
		if(x>M) A.push_back(x);
		else B.push_back(x);
	}
	sort(ALL(A));
	sort(ALL(B));
	reverse(ALL(A));
	reverse(ALL(B));
	AS.push_back(0);
	BS.push_back(0);
	FORR(x,A) AS.push_back(AS.back()+x);
	FORR(x,B) BS.push_back(BS.back()+x);
	
	ll ret=BS.back();
	for(i=1;i<=A.size();i++) {
		ll need=1LL*(i-1)*(D+1)+1;
		if(need>N) continue;
		ll v=AS[i]+BS[min((ll)B.size(),N-need)];
		ret=max(ret,v);
	}
	cout<<ret<<endl;
	
	
}

まとめ

ストーリー要るかな…。