记录编号	571847	评测结果	AAAAAAAAA
题目名称	送礼物	最终得分	100
用户昵称	00000	是否通过	通过
代码语言	C++	运行时间	3.656 s
提交时间	2022-06-25 15:25:43	内存使用	105.55 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll w,n,g[50];
ll a[20000000],aa=0,l=0;
void gh(ll x,ll y)//y重量 
{
    if(y>w) return;
    if(x>n/2)
    {
        if(y<=w) a[++aa]=y;
        return;
    }
    gh(x+1,y);
    gh(x+1,y+g[x]);
}
ll erfen(ll x,ll l,ll r)
{
    if(l==r) return a[l];
    ll d;
    d=(l+r)/2;
    if(a[d+1]>x)//不符合
    {
        return erfen(x,l,d);
     } else
     {
        return erfen(x,d+1,r);
     }
}
void gh1(ll x,ll y)//y重量 
{
    if(y>w) return;
    if(x>n-n/2)
    {
        if(y<=w)
        {
            ll k;
            k=erfen(w-y,1,aa);
            k=k+y;
            l=max(l,k);
        }
        return;
    }
    gh1(x+1,y);
    gh1(x+1,y+g[x+n/2]);
}
int main(){
freopen("giftgiving.in","r",stdin);
freopen("giftgiving.out","w",stdout);
cin>>w>>n;
for(int q=1;q<=n;q++) cin>>g[q];
gh(1,0);
sort(a+1,a+aa+1);
l=a[aa];
gh1(1,0);
cout<<l;
return 0;
}