记录编号	571864	评测结果	AAAAAAAAE
题目名称	送礼物	最终得分	88
用户昵称	cb	是否通过	未通过
代码语言	C++	运行时间	2.960 s
提交时间	2022-06-25 16:01:55	内存使用	104.02 MiB

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=(1<<23)+10;
ll n, m;
ll a[maxn], b[maxn];
ll k;
ll ans;
bool cmp (ll a, ll b)
{
    return a > b;
}
ll find (ll sum)
{
    int y = k;
    if(b[y] > m - sum)
        y = upper_bound (b + 1,b + 1 + k, m - sum) - b - 1;
    ans = max (ans, b[y] + sum);
}
int dfs (int x, ll sum)
{
    if (x == (n / 2 + 2) + 1)
    {
        b[++ k] = sum;
        return 1;
    }
    dfs (x + 1, sum);
    if (sum + a[x] <= m)
    dfs (x + 1, sum + a[x]);
}
int dfs2 (int x, ll sum)
{
    if (x == n + 1)
    {
        find (sum);
        return 1;
    }
    dfs2 (x + 1, sum);
    if (sum + a[x] <= m)
    dfs2 (x + 1, sum + a[x]);
}
int main ()
{
    freopen ("giftgiving.in", "r", stdin);
    freopen ("giftgiving.out", "w", stdout);
    scanf ("%lld %lld", &m, &n);
    for (int i = 1; i <= n; i++)
    {
        scanf ("%lld", &a[i]);
    }
    sort (a + 1, a + n + 1, cmp);
    dfs (1, 0);
    sort (b + 1, b + k + 1);
    k = unique (b + 1, b + k + 1) - (b + 1);
    dfs2 (n / 2 + 3, 0);
    printf ("%lld\n", ans);
 }