记录编号	252706	评测结果	AAAAAAAAAA
题目名称	买汽水	最终得分	100
用户昵称	_Horizon	是否通过	通过
代码语言	C++	运行时间	0.774 s
提交时间	2016-04-20 18:59:59	内存使用	7.15 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 50
using namespace std;

int n, m, a[maxn];

int b[maxn], c[maxn];

#define M 2000000
int h[M], cnt, n1, n2;
typedef long long ll;
int calcb(int S){
	ll ret = 0;
	for(int i = 1; i <= n1; i ++)
		if(S >> i-1 & 1){
			ret += b[i];
			if(ret > m)return -1;
		}
	return ret;
}

int calcc(int S){
	ll ret = 0;
	for(int i = 1; i <= n2; i ++)
		if(S >> i-1 & 1){
			ret += c[i];
			if(ret > m)return -1;
		}
	return ret;
}

int main(){
	freopen("drink.in", "r", stdin);
	freopen("drink.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++)
	    scanf("%d", &a[i]);
	n1 = n >> 1, n2 = 0;
	for(int i = 1; i <= n1; i ++)
	    b[i] = a[i];
	for(int i = n1 + 1; i <= n; i ++)
	    c[++ n2] = a[i];

	int S1 = 1 << n1, tmp;
	for(int i = 0; i < S1; i ++){
		tmp = calcb(i);
		if(~tmp) h[++ cnt] = tmp;
	}

	sort(h + 1, h + 1 + cnt);
	h[cnt + 1] = 0x7fffffff;
	int ans = 0;
	int S2 = 1 << n2;
	for(int i = 0; i < S2; i ++){
		tmp = calcc(i);
		if(tmp == -1)continue;
		int p = lower_bound(h + 1, h + 1 + cnt, m - tmp) - h;
		while(p && h[p] > m - tmp) p --;
		ans = max(ans, h[p] + tmp);
	}
	printf("%d\n", ans);
	return 0;
}