记录编号	600410	评测结果	AAAAAAAAAE
题目名称	送礼物	最终得分	90
用户昵称	wdsjl	是否通过	未通过
代码语言	C++	运行时间	3.832 s
提交时间	2025-05-04 12:03:20	内存使用	5.22 MiB

#include <iostream>
#include <algorithm>
#include <cstdio>
#define int unsigned int
using namespace std;

const int N = 50;

int n,m,a[N],w[1<<25],tl,res;

void dfs1(int st,int sum){
	if(st==n/2){
		w[tl++]=sum;
		return ;
	}
	dfs1(st+1,sum);
	if(sum+a[st]<=m){
		dfs1(st+1,sum+a[st]);
	}
	return ;
}

void dfs2(int st,int sum){
	if(st==n){
		int l=0,st=tl-1;
		while(l<st){
			int mid=(l+st+1)>>1;
			if(w[mid]<=m-sum)l=mid;
			else st=mid-1;
		}
		res=max(res,sum+w[l]);
		return;
	}
	dfs2(st+1,sum);
	if(a[st]+sum<=m){
		dfs2(st+1,sum+a[st]);
	}
}

signed main(){
	freopen("giftgiving.in","r",stdin);
	freopen("giftgiving.out","w",stdout);
	scanf("%d%d",&m,&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	sort(a,a+n);
	reverse(a,a+n);
	dfs1(0,0);
	tl=unique(w,w+tl)-w;
	sort(w,w+tl);
	dfs2(n/2,0);
	cout<<res<<endl;
	return 0;
}