CodeCraft-20 : E. Team Building

これ名前付いてるコンテストなのに商品はなかったんだな。
https://codeforces.com/contest/1316/problem/E

問題

N人の人がいるので、そこからP人の選手とK人の応援からなるチームを作りたい。
各人、選手として選ばれたときのポジション毎のスコアと、応援として選ばれた場合のスコアが与えられる。
最適な人選をしたときのスコアの最大値を求めよ。

解法

まず各人を応援としてのスコアの多い順にソートしておく。
Pが7以下なので、2^7通り各ポジションの埋まり具合に対する最大スコアを順次求めて行こう。
その際、選手でない人がK人埋まるまでは処理順に応援に加えていく。

int N,P,K;
int A[101010];
int S[101010][7];

pair<int,int> B[101010];

ll dp[101010][1<<7];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d",&N,&P,&K);
	FOR(i,N) {
		scanf("%d",&A[i]);
		B[i]={A[i],i};
	}
	FOR(i,N) FOR(j,P) scanf("%d",&S[i][j]);
	
	sort(B,B+N);
	reverse(B,B+N);
	FOR(i,N+1) FOR(j,1<<P) dp[i][j]=-1LL<<60;
	dp[0][0]=0;
	FOR(i,N) {
		int mask;
		FOR(mask,1<<j) {
			int al=i-__builtin_popcount(mask);
			if(al<K) dp[i+1][mask]=max(dp[i+1][mask],dp[i][mask]+B[i].first);
			else dp[i+1][mask]=max(dp[i+1][mask],dp[i][mask]);
			if(al<K) dp[i+1][mask]=max(dp[i+1][mask],dp[i][mask]+B[i].first);
			FOR(j,P) if((mask&(1<<j))==0) dp[i+1][mask|(1<<j)]=max(dp[i+1][mask|(1<<j)],dp[i][mask]+S[B[i].second][j]);
		}
	}
	cout<<dp[N][(1<<P)-1]<<endl;
	
}

まとめ

Div2とはいえEの割に簡単？