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

#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long ll;
using ::std::vector;
using ::std::sort;
using ::std::max;

const int MAXN = 60;

ll w, n;
ll a[MAXN];
vector <ll> A, B;
ll maxx;

void dfs1(int pos, ll now) {
	if (pos > n / 2) {
		A.push_back(now);
		return ;
	}
	if (now + a[pos] <= w) dfs1(pos + 1, now + a[pos]);
	dfs1(pos + 1, now);
}

void dfs2(int pos, ll now) {
	if (pos > n) {
		B.push_back(now);
		return ;
	}
	if (now + a[pos] <= w) dfs2(pos + 1, now + a[pos]);
	dfs2(pos + 1, now);
}

int main() {
	freopen("giftgiving.in", "r", stdin);
	freopen("giftgiving.out", "w", stdout);
	scanf("%lld %lld", &w, &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	dfs1(1, 0);
	dfs2(n / 2 + 1, 0);
	sort(B.begin(), B.end());
	for (auto x : A) {
		ll l = 0, r = B.size() - 1, ans = 0;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (x + B[mid] <= w) {
				ans = B[mid];
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		maxx = max(maxx, x + ans);
	}
	printf("%lld", maxx);
	return 0;
}