2016-2017 National Taiwan University World Final Team Selection Contest

結構前のコンテストですが、G問題がシンプルだけどどこか新鮮で面白かったので紹介します
Dashboard - 2016-2017 National Taiwan University World Final Team Selection Contest - Codeforces

概要
N個(値段:p_i)の空でない部分集合であってK番目に値段の和が小さいものを求めよ(復元なし)
2 ≤ N ≤ 2 × 10^5
1 ≤ K ≤ min(10^6, 2^N - 1)
1 ≤ p_i ≤ 10^8

解法
まずpを小さい順にソートします。もちろん2^N通り全列挙は出来ないのと、Kはあまり大きくないので、小さい順に列挙することを考えます。
ここで、ある集合の1番右のものの次を続けて使うorある集合の1番右をやめてその右隣を使うという遷移をすることにすると、価値が単調に増加するように遷移出来て嬉しいことがわかります。(イメージしにくいですが)
よって、priority_queue等で管理しつつ遷移していくことでO(KlogK)で解くことが出来ました。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const int MN = 200010;

int N, K;
int p[MN];

int main() {
	scanf("%d %d", &N, &K);
	rep(i, N) scanf("%d", &p[i]);
	sort(p, p + N);

	using Data = pair<ll, int>;
	priority_queue<Data, vector<Data>, greater<Data>> que;

	que.push(mp(0LL, -1));

	ll la = -1;
	++K;

	while (K--) {
		Data t = que.top(); que.pop();

		ll val = t.fi;
		int pos = t.se;

		la = val;

		if (pos == N-1) continue;

		//add next
		que.push(mp(t.fi + p[pos + 1], pos + 1));

		//replace
		if (pos != -1) {
			que.push(mp(t.fi + p[pos + 1] - p[pos], pos + 1));
		}
	}

	cout << la << endl;

	return 0;
}