fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long ans = 0;
  5.  
  6. void subproblem(vector<int>::iterator s, vector<int>::iterator e, long long goal, unordered_map<int, long long> &miss)
  7. {
  8.     int n = e - s;
  9.     for (int mask = 1; mask < (1 << n); mask++)
  10.     {
  11.         long long sum = 0;
  12.         for (int j = 0; j < n; j++)
  13.             sum += mask & (1 << j) ? *(s + j) : 0;
  14.  
  15.         if (sum == goal)
  16.             ans++;
  17.         else if (sum < goal)
  18.             miss[sum]++;
  19.     }
  20. }
  21.  
  22. void solve()
  23. {
  24.     int n, x;
  25.     cin >> n >> x;
  26.     vector<int> t(n);
  27.     for (auto &i : t)
  28.         cin >> i;
  29.     sort(t.begin(), t.end());
  30.  
  31.     int m = n / 2;
  32.     unordered_map<int, long long> mp1, mp2;
  33.     subproblem(t.begin(), t.begin() + m, x, mp1);
  34.     subproblem(t.begin() + m, t.end(), x, mp2);
  35.  
  36.     for (auto [sum, v] : mp1)
  37.     {
  38.         if (mp2.find(x - sum) != mp2.end())
  39.             ans += v * mp2[x - sum];
  40.     }
  41.  
  42.     cout << ans << "\n";
  43. }
  44.  
  45. int main()
  46. {
  47.     ios::sync_with_stdio(false);
  48.     cin.tie(0);
  49.     cout.tie(0);
  50.  
  51.     int t = 1;
  52.     // cin >> t;
  53.     while (t--)
  54.         solve();
  55. }
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/rP9r2y
language:
C++ (gcc 8.3)
created:
55 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!