记录编号	252478	评测结果	AAAAAAAAAA
题目名称	买汽水	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.290 s
提交时间	2016-04-20 15:57:47	内存使用	0.31 MiB

//KZNS
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
//
ifstream fin ("drink.in");
ofstream fout ("drink.out");
//
int N;
int Dls[50];
int DFSl, DFSr, Ded;
vector<int> edl[2];
int M;
int MX = 0;
//
void DFS(int x, int v) {
	if (v > M)
		return;
	if (x > DFSr) {
		MX = max(MX, v);
		edl[Ded].push_back(v);
		return;
	}
	DFS(x+1, v);
	DFS(x+1, v+Dls[x]);
}
//
int main() {
	fin >> N >> M;
	for (int i = 1; i <= N; i++)
		fin >> Dls[i];
	if (N < 20) {
		DFSl = 1;
		DFSr = N;
		Ded = 0;
		DFS(DFSl, 0);
		fout << MX;
		return 0;
	}
	else {
		DFSl = 1;
		DFSr = N/2;
		Ded = 0;
		DFS(DFSl, 0);
		sort(edl[0].begin(), edl[0].end());
		DFSl = DFSr+1;
		DFSr = N;
		Ded = 1;
		DFS(DFSl, 0);
		sort(edl[1].begin(), edl[1].end());
		int i = 0,j = edl[1].size()-1;
		for (i = 0; i < edl[0].size(); i++) {
			if (j < 0)
				break;
			for (;j >= 0; j--) {
				if (edl[0][i] + edl[1][j] <= M) {
					MX = max(MX, edl[0][i]+edl[1][j]);
					break;
				}
			}
		}
		fout << MX;
		return 0;
	}
	return 0;
}
//UBWH