fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define Long long long
  6. #define bint __int128
  7. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  8.  
  9. #include <ext/pb_ds/assoc_container.hpp>
  10.  
  11. using namespace __gnu_pbds;
  12.  
  13. struct custom_hash {
  14.     static uint64_t splitmix64(uint64_t x) {
  15.         x = x + 0x9e3779b97f4a7c15;
  16.         x = ( x ^ (x >> 30) ) * 0xbf58476d1ce4e5b9;
  17.         x = ( x ^ (x >> 27) ) * 0x94d049bb133111eb;
  18.         return x ^ (x >> 31);
  19.     }
  20.  
  21.     size_t operator()(uint64_t x) const {
  22.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  23.         return splitmix64(x + FIXED_RANDOM);
  24.     }
  25. };
  26.  
  27. template <class K, class V> using HT = gp_hash_table<K, V, custom_hash>;
  28.  
  29. void get_shit_done() {
  30.     int n, x;
  31.     cin >> n >> x;
  32.  
  33.     vector<int> t(n);
  34.     for (int i = 0; i < n; ++i) {
  35.         cin >> t[i];
  36.     }
  37.  
  38.     int l = n / 2, r = (n + 1) / 2;
  39.  
  40.     HT<Long, int> freqLeft;
  41.     for (int mask = 0; mask < (1 << l); ++mask) {
  42.         Long sum = 0;
  43.         bitset<50> bt(mask);
  44.         for (int i = 0; i < l; ++i) {
  45.             if (bt[i]) {
  46.                 sum += t[i];
  47.             }
  48.         }
  49.         ++freqLeft[sum];
  50.     }
  51.  
  52.     Long ans = 0;
  53.     for (int mask = 0; mask < (1 << r); ++mask) {
  54.         Long sum = 0;
  55.         bitset<50> bt(mask);
  56.         for (int i = l; i < n; ++i) {
  57.             if (bt[i - l]) {
  58.                 sum += t[i];
  59.             }
  60.         }
  61.         ans += freqLeft[x - sum];
  62.     }
  63.  
  64.     cout << ans;
  65. }
  66.  
  67. signed main() {
  68.     _3bkarm
  69.  
  70.     int ts = 1;
  71. //    cin >> ts;
  72.     while (ts--) {
  73.         get_shit_done();
  74.     }
  75.  
  76.     return 0;
  77. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/bj5v88
language:
C++ (gcc 8.3)
created:
10 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!