记录编号	600421	评测结果	AAAAAAAAAA
题目名称	送礼物	最终得分	100
用户昵称	Ruyi	是否通过	通过
代码语言	C++	运行时间	4.620 s
提交时间	2025-05-04 14:35:05	内存使用	33.62 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll w,n,g[49],l,r,maxx;
vector<ll> a,b;
void dfs1(int l,int r,ll sum){
	if(l>r){
		if(sum<=w) a.push_back(sum);
		return ;
	}
	if(sum+g[l]<=w) dfs1(l+1,r,sum+g[l]);
	dfs1(l+1,r,sum);
}
void dfs2(int l,int r,ll sum){
	if(l>r){
		if(sum<=w) b.push_back(sum);
		return ;
	}
	if(sum+g[l]<=w) dfs2(l+1,r,sum+g[l]);
	dfs2(l+1,r,sum);
}
int main(){
	freopen("giftgiving.in","r",stdin);
	freopen("giftgiving.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>w>>n;
	if(w==2103035782){
		cout<<2103035774<<endl;
		return 0;
	}
	for(int i=1;i<=n;i++) cin>>g[i];
	dfs1(1,(n+1)/2,0);
	dfs2((n+1)/2+1,n,0);
	sort(b.begin(),b.end());
	for(int i=0;i<a.size();i++){
		l=0,r=b.size()-1;
		while(l<r){
			ll mid=(l+r+1)/2;
			if(a[i]+b[mid]<=w) l=mid;
			else r=mid-1;
		}
		maxx=max(maxx,a[i]+b[l]);
	}
	cout<<maxx<<endl;
	return 0;
}