Submission #1357589

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define int long long
int w[50];
int pw[1<<17];
signed main(){
	int n,x;
	cin>>n>>x;
	for(int i=1;i<=n;i++)cin>>w[i];
	n+=2;
	int n2=n/2;
	for(int i=0;i<1<<n2;i++){
		int sw=0;
		for(int j=0;j<n2;j++){
			if(i>>j&1){
				sw+=w[j];
				}
			}
			pw[i]=sw;
		}
		
	sort(pw,pw+(1<<n2));	
	
	int res=0;
	for(int i=0;i<1<<(n-n2);i++){
		int sw=0;
		for(int j=0;j<n-n2;j++){
			if(i>>j&1){
				sw+=w[n2+j];
				}
			}
			if(sw<=x){
				auto itr=equal_range(pw,pw+n,x-sw);
				res+=*itr.second-*itr.first;
				}
		}
		cout<<res<<endl;
	}

Submission Info

Judge Result