记录编号	589193	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	挑战 NPH	最终得分	100
用户昵称	darkMoon	是否通过	通过
代码语言	C++	运行时间	3.365 s
提交时间	2024-07-03 17:22:13	内存使用	21.04 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
auto mread = [](){int x;scanf("%lld", &x);return x;};
int t = mread(), a[1005], f[10000005];
signed main(){
    while(t --){
        int n = mread(), k = mread();
        int sum = 0;
        for(int i = 1; i <= n; i ++){
            a[i] = mread();
            sum += a[i];
        }
        if(n == 1){
            printf("%lld\n", k * a[1]);
        }
        else if(n == 2){
            int m = sum * ceil(pow(k, 1.0 / (double)n));
            signed l = 1, r = m, x, y, ma;
            int sum;
            while(l < r){
                signed mid = (l + r) >> 1;
                x = a[1], y = a[2];
                if(x < y)
                swap(x, y);
                ma = mid / x, sum = 0;
                for(signed i = 1; i <= ma; i ++){
                    sum += (mid - i * x) / y;
                }
                sum += mid / x + mid / y;
                if(sum >= k)
                r = mid;
                else
                l = mid + 1;
            }
            printf("%lld \n", l);
        }
        else{
            int m = sum * ceil(pow(k, 1.0 / (double)n));
            for(int i = 1; i <= m; i ++)
            f[i] = 0;
            f[0] = 1;
            for(int i = 1; i <= n; i ++){
                for(int j = a[i]; j <= m; j ++){
                    f[j] += f[j - a[i]];
                    if(f[j] >= 1e12)
                    f[j] = 1e12;
                }
            }
            int sum = 0;
            for(int i = 1; i <= m; i ++){
                sum += f[i];
                if(sum >= k){
                    printf("%lld\n", i);
                    break;
                }
            }
        }
    }
    return 0;
}