Submission #73185547

---

Source Code Expand

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using i128 = __int128;
using u128 = unsigned __int128;

mt19937_64 mrand((u64)random_device{}() << 32 ^ random_device{}() ^
	chrono::high_resolution_clock::now().time_since_epoch().count());
template<class T = i64,class T2>T rnd(T l,T2 r){
return uniform_int_distribution<T>(l,r)(mrand);}

int main (){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	int n;
	i64 s;

	cin >> n >> s;

	vector<i64> a(n + 1);

	for (int i = 0;i < n;i++)
		cin >> a[i];

	unordered_map<i64,int> cnt;
	
	for (int i = 0;i < 1 << n / 2;i++){
		i64 v = 0;

		for (int j = i;j;j -= j & -j)
			v += a[__lg(j & -j)];

		cnt[v]++;
	}

	i64 ans = 0;

	for (i64 i = 0;i < 1LL << n;i += 1 << n / 2){
		i64 v = 0;

		for (i64 j = i;j;j -= j & -j)
			v += a[__lg(j & -j)];
			
		ans += cnt[s - v];
	}

	cout << ans;
}

Submission Info

Judge Result