记录编号	589215	评测结果	AAAAAAAAAAAAAEEEEETA
题目名称	挑战 NPH	最终得分	70
用户昵称	flyfree	是否通过	未通过
代码语言	C++	运行时间	7.355 s
提交时间	2024-07-03 18:00:40	内存使用	61.53 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int T;
ll w[1005],n,k,s;
ll w1,w2;
ll bag[10000005];
int ef(){
    ll l=1,r=(w1+w2)*sqrt(k);
    while(l<r){
        ll mid=(l+r)/2;
        ll ans=0;
        for(ll i=0;i<=(mid/w1);i++){
            ans+=(mid-i*w1)/w2+1;
        }
        ans-=1;
        if(ans>=k)r=mid;
        else l=mid+1;
    }
    return l;
}
int main(){
    freopen("NPH.in","r",stdin);
    freopen("NPH.out","w",stdout);
    cin>>T;
    for(ll tm=1;tm<=T;tm++){
        cin>>n>>k;
        if(n==1){
            ll x;
            cin>>x;
            cout<<x*k<<endl;
        }else if(n==2){
            cin>>w1>>w2;
            if(w1<w2)swap(w1,w2); 
            cout<<ef()<<endl;
        }else{
//            memset(bag,0,sizeof(bag));
            bag[0]=1;
            for(int i=1;i<=n;i++){
                cin>>w[i];
                s+=w[i];
            }
            int len=pow(k,(1.0)/(double)n)*s;
            for(int i=1;i<=n;i++)for(int j=w[i];j<=len;j++){
                bag[j]+=bag[j-w[i]];
            }
            ll ans=0;
            while(k>0){
                ans++;
                k-=bag[ans];
//                cout<<bag[ans]<<endl;
            }
            cout<<ans<<endl;
            for(int j=0;j<=len;j++)bag[j]=0;
        } 
    } 
    return 0;
}