yukicoder : No.2370 He ate many cakes

これはすんなりだった。
https://yukicoder.me/problems/no/2370

問題

N個の整数が与えられる。
これらのうちいくつか選んでその総和を取ると、重複を含め2^N通りの総和が考えられる。
そのうち大きい順からK番目の値は何か。

解法

総和の上位K位までを保持しながら、各整数を足す場合と足さない場合を考え数列を倍化していくとよい。

int N,K;
int A[33];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	vector<ll> V={0};
	FOR(i,N) {
		cin>>x;
		y=V.size();
		FOR(j,y) V.push_back(V[j]+x);
		sort(ALL(V));
		reverse(ALL(V));
		if(V.size()>K) V.resize(K);
	}
	cout<<V.back()<<endl;
}

まとめ

Kが小さいことに気付けば楽。