小さいほうから順に構成していく. \(x\) 円が作れるとき,どの様な作り方かは無関係に \(x + a[i]\) 円が作れる. 作れる値全体を保管する set を用意すればよい.
実装
今調べている場所をiterator で持っておいてもよいし, 調べ終わったら set から erase してもよい.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, k ;
cin >> n >> k;
vll a(n); rep(i,n) { cin >> a[i]; }
set<ll> st;
st.insert(0);
ll c = 0;
auto it = st.begin();
while(c < k){
ll x = *it;
rep(i,n){
st.insert(x + a[i]);
}
c++;
it++;
}
cout << *it << endl;
return 0;
}