Submission #73190534

---

Source Code Expand

#include <bits/stdc++.h>
using ll = long long int;
using namespace std;
ll read()
{
    ll k = 0,f = 1;
    char c = getchar();
    while(c < '0' || c > '9')
    {
        if(c == '-')f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')k = k * 10 + c - '0',c = getchar();
    return k * f; // 别忘记标记的负数要乘进去
}
// 调用时用 n=in();
void print(ll x)
{
    if(x < 0)putchar('-'),x = -x;
    if(x < 10)putchar(x + '0');
    else print(x / 10),putchar(x % 10 + '0');
}
// 直接调用 out(n) 就行了
void solve(){
    ll n = read();
    ll S = read();
    vector<ll>a(n + 1);
    for(int i = 1; i <= n; i++){
        a[i] = read();
    }
    unordered_map<ll, ll>left;
    unordered_map<ll, ll>right;
    ll ans = 0;
    // [1, n / 2];
    // [n / 2 + 1, n];
    auto dfs = [&](auto&& self, int pos, int ed, ll sum, unordered_map<ll, ll>&mp) -> void{
        if(pos > ed){
            mp[sum]++;
            return;
        }
        self(self, pos + 1, ed, sum, mp);
        self(self, pos + 1, ed, sum + a[pos], mp);
    };
    dfs(dfs, 1, n / 2, 0, left);
    dfs(dfs, n / 2 + 1, n, 0, right);
    for(auto [key, val] : left){
        if(right.count(S - key)){
            ans += right[S - key] * val;
        }
    }
    cout << ans;
}
signed main(){
    int T = 1;
    while(T--){
        solve();
    }
    return 0;
}

Submission Info

Judge Result