Atcoder Beginner Contest 184 F Programming Contest(暴力枚举+二分）

题意：
高桥将参加编程竞赛，竞赛持续了T分钟，并提出了V问题。
凭借他的超感官知觉，他已经知道它将需要ai分钟解决第i个问题。
他将从N个问题中选择零个或多个要解决的问题，因此解决这些问题所花费的总时间不会超过T分钟。
找到他解决问题选择所需的最长时间。
1<=N<=40
1<=T<=10^9
1<=a[i]<=10^9
题解：
看到数据范围首先想到枚举2^N,发现肯定会超时。于是我们可以将N分成两半，然后分别枚举子集，得到两个集合。然后对两个集合的进行二分求出最大的所需时间。时间复杂度为$2^{N/2}$log$2^{N/2}$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005;
ll n,t,ans;
ll a[N];
set<ll>ss;
int main() {
	cin>>n>>t;
	for(int i=0;i<n;i++) {
		cin>>a[i];
	}
	
	for(int x=0;x<(1<<(n/2));x++) {
		ll sum=0;
		for(int i=0;i<n/2;i++) {
			if(x&(1<<i)) sum+=a[i];
		}
		if(sum<=t) ss.insert(sum);
	}
	
	for(int x=0;x<(1<<(n-n/2));x++) {
		ll sum=0;
		for(int i=0;i<n-n/2;i++) {
			if(x&(1<<i)) sum+=a[n/2+i];
		}
		if(sum<=t) ans = max(ans,sum+*(--ss.upper_bound(t-sum)));
	}
	
	cout<<ans<<endl;
	return 0;
}