Shared code

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(false); cin.tie(0);
#define endl '\n'
 
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b, c) for (int i = a; i < b; i += c)
#define Each(i, v) for (auto& i : v)
 
#define mp(a, b) make_pair(a, b)
#define F first
#define S second

using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
// template<typename T1, typename T2>
// ostream& operator<<(ostream& os, const pair<T1, T2> &a) {
//     return os << "(" << a.first << ", " << a.second << ")";
// }
 
/* ------------------------------------------- */
 
const int maxn = (1<<20) + 1;
const int INF = 2e9;
const ll LLINF = 1e18;
const ll MOD = 1e9 + 7;
 
const int MX = 1e9 + 1;
 
 
inline int lb(int& x) {
    return x & (-x);
}
 
 
int n, na, nb; int x;
vector<int> v, a, b;
int ma[maxn], mb[maxn], maptr = 0, mbptr = 0;
int sa[maxn], sb[maxn];
short lg[maxn];


void init() {
    REP(i, 20) lg[1<<i] = i;
    
    cin >> n >> x;
    v.clear();
    REP(i, n) {
        ll t; cin >> t;
        if (t > x) continue;
        v.emplace_back(t);
    }
    sort(v.begin(), v.end());
    n = (int)v.size();
    REP(i, n/2) {
        a.emplace_back(v.back());
        v.pop_back();
    }
    Each(t, v) b.emplace_back(t);
    na = (int)a.size();
    nb = (int)b.size();
}


void solve() {
    int l;
    ll ans = 0;
    
    FOR(msk, 1, 1<<na, 1) {
        l = lb(msk);
        sa[msk] = sa[msk^l] + a[lg[l]];
        if (sa[msk] == x) ans++;
        else if (sa[msk] < x) ma[maptr++] = sa[msk];
    }
    FOR(msk, 1, 1<<nb, 1) {
        l = lb(msk);
        sb[msk] = sb[msk^l] + b[lg[l]];
        if (sb[msk] == x) ans++;
        else if (sb[msk] < x) mb[mbptr++] = sb[msk];
    }
    sort(ma, ma+maptr);
    sort(mb, mb+mbptr);
    
    for (int i = maptr-1, up = 0, low = 0; i >= 0; i--) {
        while (low < mbptr && ma[i] + mb[low] < x) low++;
        up = max(low, up);
        while (up < mbptr && ma[i] + mb[up] <= x) up++;
        ans += up-low;
    }
    
    cout << ans << endl;
}
 
 
int main() {
    fastio
    
    init();
    solve();
 
    return 0;
}
/*
 
 
4 5
1 2 3 2
 
 
 
 
 
 
 
 
 
 
 */