记录编号	601512	评测结果	AAWWWWAAAAAATTTTTTTW
题目名称	3992.挑战 NPH	最终得分	40
用户昵称	健康铀	是否通过	未通过
代码语言	C++	运行时间	31.307 s
提交时间	2025-06-25 16:57:42	内存使用	4.04 MiB

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

const ll P = 1e9 + 7;
const int U = 10000000;

int main() {
    auto rd = [] {
        ll x = 0, f = 1; char c = getchar();
        for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
        for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
        return x * f;
    };

    freopen("NPH.in", "r", stdin);
    freopen("NPH.out", "w", stdout);

    ll t = rd();
    while (t--) {
        ll n = rd(), k = rd();
        vector<ll> c(n);
        for (ll i = 0; i < n; i++) c[i] = rd();

        if (n == 1) {
            printf("%lld\n", c[0] * k);
            continue;
        }

        if (n == 2) {
            ll a = c[0], b = c[1];
            if (a > b) swap(a, b);
            
            auto cal = [&](ll m) {
                ll s = m / a + m / b;
                for (ll i = 1; i <= m / a; i++)
                    s += (m - a * i) / b;
                return s;
            };
            
            ll l = 1, r = (a + b) * static_cast<ll>(sqrt(k)) + 100;
            while (l < r) {
                ll m = (l + r) / 2;
                cal(m) >= k ? r = m : l = m + 1;
            }
            printf("%lld\n", l);
            continue;
        }

        ll s = 0;
        for (ll x : c) s += x;
        ll m = min(s * static_cast<ll>(ceil(pow(k, 1.0 / n))), static_cast<ll>(U));
        
        vector<ll> f(m + 1, 0);
        f[0] = 1;
        
        for (ll x : c) {
            for (ll j = x; j <= m; j++) {
                f[j] = (f[j] + f[j - x]) % P;
            }
        }
        
        ll r = k;
        for (ll i = 1; i <= m; i++) {
            if (r <= f[i]) {
                printf("%lld\n", i);
                break;
            }
            r -= f[i];
        }
    }
    return 0;
}