# [2014-10-29 模拟赛] 买汽水

3 77567506
10856 8595 24637

44088

NOIP 模拟赛

## 代码 Code

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
#define ll long long
const int inf=0x7fffffff/27.11;
int i,j,t,n,m,l,r,k;
int a[45];
vector <int> v;
ll z,y,x,ans=0;
void dfs(int s)
{
int i,j,t;
if (s==n>>1)
{
if ((ll)x+a[s]<=m) v.push_back(x+a[s]);
v.push_back(x);
return ;
}
if (s==n)
{
x+=a[s];
if (x<=m)
{
t=lower_bound(v.begin(),v.end(),m-x)-v.begin();
if (t==v.size() || v[t]+x>m) t--;
if (t>=0) ans=max(ans,v[t]+x);
}
x-=a[s];
if (x<=m)
{
t=lower_bound(v.begin(),v.end(),m-x)-v.begin();
if (t==v.size() || v[t]+x>m) t--;
if (t>=0) ans=max(ans,v[t]+x);
}
return ;
}
x+=a[s];
if (x<=m) dfs(s+1);
x-=a[s];
if (x<=m) dfs(s+1);
}
int main()
{
freopen("drink.in","r",stdin);
freopen("drink.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
v.clear();
x=0;
dfs(1);
sort(v.begin(),v.end());
x=0;
dfs((n>>1)+1);
printf("%d\n",ans);
return 0;
}``````