记录编号	585210	评测结果	AAAAAAAAAT
题目名称	送礼物	最终得分	90
用户昵称	┭┮﹏┭┮	是否通过	未通过
代码语言	C++	运行时间	7.020 s
提交时间	2023-11-28 19:47:19	内存使用	49.41 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define P pair<int,int> 
const int N = 50,M = 17e6+10;
int n;
int a[N],s[M],m,ans,cnt;
void dfs1(int x,int sum){
    if(x == n/2+1){
        s[++cnt] = sum;
        return;
    }
    if(sum <= m - a[x])dfs1(x+1,sum+a[x]);
    dfs1(x+1,sum);
}
int find(int x){
    int l = 1,r = cnt;
    while(l <= r){
        int mid = l + r >> 1;
        if(s[mid] <= x)l = mid+1;
        else r = mid-1;
    }
    return s[r];
}
void dfs2(int x,int sum){ 
    if(x == n+1){
        ans = max(ans,sum + find(m-sum));
        return;
    }
    if(sum <= m - a[x])dfs2(x+1,sum+a[x]);
    dfs2(x+1,sum);
}
int main(){
    freopen("giftgiving.in","r",stdin);
    freopen("giftgiving.out","w",stdout);
    scanf("%u%d",&m,&n);
    for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
    dfs1(1,0);
    sort(s+1,s+1+cnt);
    cnt = unique(s+1,s+1+cnt) - (s+1);
    ans = s[cnt];
    dfs2(n/2+1,0);
    printf("%u\n",ans);
    
    return 0;
    
}