Submission #29772327

---

Source Code Expand

#include<bits/stdc++.h>
#define int long long
using namespace std;
template <class T> inline T read(){
	T r=0,f=0;char c=getchar();
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) r=(r<<3)+(r<<1)+(c^48),c=getchar();
	return f?-r:r;
}
const int _=45;
int n,t,a[_],ans;
vector<int> p1,p2;
void dfs(int x,int ed,int sum,vector<int> &V){
	if(sum>t) return;
	if(x>ed){ans=max(ans,sum),V.push_back(sum);return;}
	dfs(x+1,ed,sum,V);
	dfs(x+1,ed,sum+a[x],V);
}
signed main(){
	n=read<int>(),t=read<int>();
	for(int i=1;i<=n;++i) a[i]=read<int>();
	dfs(1,n/2,0,p1),dfs(n/2+1,n,0,p2);
	sort(p2.begin(),p2.end());
	for(auto v:p1) ans=max(ans,v+p2[upper_bound(p2.begin(),p2.end(),t-v)-p2.begin()-1]);
	printf("%lld",ans);
	return 0;
}

Submission Info

Judge Result