AtCoder ABC 297 E - Kth Takoyaki Set (1Q, 緑色, 500 点)

よくある priority queue の使い方！

• 問題へのリンク

問題概要

個の正の整数 から重複を許して何個か選んだ総和として考えられる値のうち、小さい方から 番目の値を求めよ。

制約

• 
• 

考えたこと

この手の priority queue の使い方はよくある。「小さい順に 個を求める」という局面で、よく登場する。

最初にキューに 0 を挿入しておいて、次のようにすればよい。

---

• 新規の値が取り出されるまで、キューから値を取り出すことを繰り返す（すでにみた値は捨てていく）
• 新規の値が 個目であれば、それを出力して終了する
• そうでなければ、新規の値に対して、 を足した値をキューに挿入していく

---

計算量は となる。

コード

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

template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); }
template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); }

using pint = pair<int, int>;
using pll = pair<long long, long long>;
using tint = array<int, 3>;
using tll = array<long long, 3>;
using vll = vector<long long>;
using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using int128 = __int128;
using u128 = unsigned __int128;
template <class T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

#define REP(i, a) for (long long i = 0; i < (long long)(a); i++)
#define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++)
#define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i)
#define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i)
#define EB emplace_back
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define FI first
#define SE second
#define ALL(x) x.begin(), x.end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

int main() {
    int N, K;
    cin >> N >> K;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];

    min_priority_queue<ll> que;
    set<ll> S;
    REP(i, N) que.push(A[i]);
    while (S.size() < K) {
        auto val = que.top();
        que.pop();
        if (S.count(val)) continue;
        S.insert(val);
        REP(i, N) que.push(val + A[i]);
    }
    cout << *S.rbegin() << endl;
}