P5194(一道黄题)

#include<bits/stdc++.h>
#define ll long long 

using namespace std;

ll n, c, a[1010], maxx, v[1010], flag = 0;

void init()
{
	cin >> n >> c;
	for(int i = 1; i <= n; ++i)
	{
		cin >> a[i];
		if(a[i] == c)
		{
			cout << c << endl;
			flag = 1;
		}
		if(a[i] > c)
			v[i] = 1;
	}
}

int binary_search(ll x, ll tmp)
{
	ll l = 1, r = x;
	while(l < r)
	{
		int mid = l + r + 1>> 1;
		if(a[mid] > tmp)
			r = mid-1;
		else
			l = mid;
	}
	return l;
}

void dfs(ll ans, ll x)
{
	if(ans > c)
		return;
	else
		maxx = max(maxx, ans);
	int d = x;
	if(!v[x])
		d = binary_search(x, c-ans);
	for(int i = d; i >= 1; --i)
	{
		if(!v[i])
		{
			v[i] = 1;
			dfs(ans+a[i], i);
			v[i] = 0;
		}
	}
	return;
}

int main()
{
	init();
	if(flag)
		return 0;
	dfs(0, n);
	cout << maxx << endl;
	return 0;
}