记录编号	571814	评测结果	AAAAAAAAA
题目名称	送礼物	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	4.970 s
提交时间	2022-06-25 11:22:54	内存使用	104.02 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=45+5;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f;
int n;
ll g[N],w,ans=0;
ll p[1<<24]={0};
bool cmp(ll x,ll y){
    return x>y;
}
void dfs(int pt,ll num){
    if (num>w)return ;
    if (pt==n/2+3){
        p[++p[0]]=num;
        return ;
    }
    dfs(pt+1,num);
    dfs(pt+1,num+g[pt]);
    return ;
}
void findsum(ll t){
    ll l=1,r=p[0]+1;
    while(l<r){
        int mid=(l+r)/2;
        if (p[mid]>t)r=mid;
        else l=mid+1;
    }
    ans=max(ans,w-t+p[l-1]);
    return ;
}
void dfs2(int pt,ll num){
    if (num>w)return ;
    if (pt==n+1){
        findsum(w-num);
        return ;
    }
    dfs2(pt+1,num);
    dfs2(pt+1,num+g[pt]);
    return ;
}
int main(){
    freopen ("giftgiving.in","r",stdin);
    freopen ("giftgiving.out","w",stdout);
    scanf("%lld%d",&w,&n);
    for (int i=1;i<=n;i++){
        scanf("%lld",&g[i]);
    }
    sort(g+1,g+n+1,cmp);
    dfs(1,0);
    sort(p+1,p+p[0]+1);
    int q=0;
    for (int i=1;i<=p[0];i++){
        if (p[i]==p[i-1])q++;
        else p[i-q]=p[i];
    }
    p[0]-=q;
    p[++p[0]]=inf;
    dfs2(n/2+3,0);
    printf("%lld\n",ans);
    return 0;
}