记录编号	600442	评测结果	AAAAAAAAAA
题目名称	送礼物	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	4.532 s
提交时间	2025-05-04 14:46:17	内存使用	34.57 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll w,n,a[110],ans;
vector<ll>v1,v2;
void dfs1 (int idx,ll sum) {
	if (idx>n/2) {
		v1.push_back(sum);
		return;
	}
	if (sum+a[idx]<=w) dfs1(idx+1,sum+a[idx]);
	dfs1(idx+1,sum);
}
void dfs2 (int idx,ll sum) {
	if (idx>n) {
		v2.push_back(sum);
		return;
	}
	if (sum+a[idx]<=w) dfs2(idx+1,sum+a[idx]);
	dfs2(idx+1,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;
	for (int i=1;i<=n;i++) cin >> a[i];
	dfs1(1,0),dfs2(n/2+1,0);
	sort(v1.begin(),v1.end());
	for (int i=0;i<v2.size();i++) {
		ll l=0,r=v1.size()-1,sum=v2[i];
		while (l<r) {
			ll mid=(l+r+1)/2;
			if (sum+v1[mid]<=w) l=mid;
			else r=mid-1; 
		}
		ans=max(ans,sum+v1[l]);
	}
	cout << ans <<endl;
	return 0;
}