记录编号	571844	评测结果	AAAAAAAAA
题目名称	送礼物	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	3.032 s
提交时间	2022-06-25 15:15:52	内存使用	54.69 MiB

#include <bits/stdc++.h>
#define int unsigned int
using namespace std;
const int maxn = 50;
const int maxm = 20000000;
int a[maxn],w,n,ans;
int s[maxm],cnt;
void dfs(int x,int t,int cur) {
    if(x > t){s[++ cnt] = cur;return ;}
    if(w - cur >= a[x])dfs(x + 1 , t , cur + a[x]);
    dfs(x + 1 , t , cur);
    return ;
}
int Find(int x) {
    int l = 1,r = cnt,mid;
    while(l <= r) {
        mid = l + r >> 1;
        if(s[mid] <= x)l = mid + 1;
        else r = mid - 1;
    }
    return s[r];
}
void DFS(int x,int t,int cur) {
    if(x > t){ans = max(ans , cur + Find(w - cur));return ;}
    if(w - cur >= a[x])DFS(x + 1 , t , cur + a[x]);
    DFS(x + 1 , t , cur);
    return ;
}
signed main() {
    freopen("giftgiving.in","r",stdin);
    freopen("giftgiving.out","w",stdout);
    scanf("%u%d",&w,&n);
    for(int i = 1;i <= n;++ i)scanf("%u",&a[i]);
    dfs(1 , n / 2 , 0);
    sort(s + 1 , s + 1 + cnt);
    cnt = unique(s + 1 , s + 1 + cnt) - s - 1;
    ans = s[cnt];
    DFS(n / 2 + 1 , n , 0);
    printf("%u\n",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}