记录编号	600459	评测结果	AAAAAAAAAT
题目名称	送礼物	最终得分	90
用户昵称	会挽弯弓满月	是否通过	未通过
代码语言	C++	运行时间	9.193 s
提交时间	2025-05-04 15:56:21	内存使用	33.61 MiB

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1<<25;
ll w,n;
ll g[50];
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return f*x;
}
vector<ll> a,b;
void dfs1(int l,int r,ll sum){
	if(l>r){
		if(sum<=w) a.push_back(sum);
		return;
	}
	dfs1(l+1,r,sum+g[l]);
	dfs1(l+1,r,sum);
	return;
}
void dfs2(int l,int r,ll sum){
	if(l>r){
		if(sum<=w) b.push_back(sum);
		return;
	}
	dfs2(l+1,r,sum+g[l]);
	dfs2(l+1,r,sum);
	return;
}
int main(){
	freopen("giftgiving.in","r",stdin);
	freopen("giftgiving.out","w",stdout);
	w=read();n=read();
	for(int i=1;i<=n;i++){
		g[i]=read();
	}
	dfs1(1,(1+n)/2,0);
	dfs2((1+n)/2+1,n,0);
	sort(b.begin(),b.end());
	int l,r,ans,mid;
	ll maxn=0,sum;
	for(int i=0;i<a.size();i++){
		sum=a[i];
		l=0;r=b.size()-1;ans=0;
		while(l<=r){
			mid=(l+r)>>1;
			if(b[mid]+a[i]<=w){
				l=mid+1;
				ans=mid;
			}
			else r=mid-1;
		}
		sum+=b[ans];
		maxn=max(maxn,sum);
	}
	printf("%lld",maxn);
	return 0;
}