Submission #60637986

---

Source Code Expand

#pragma GCC optimize("O3", "Ofast", "unroll-loops")
#include <bits/stdc++.h>
 
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ln '\n'
#define sep ' '
#define ve vector

using namespace std;
 
using pii = pair<int, int>;
using ll  = long long;
using ull = unsigned ll;

int n, m, x;

void solve()
{
  cin >> n >> x;

  ve<int> a(n / 2);
  for (auto &x : a) cin >> x;

  ve<int> b(n - n / 2);
  for (auto &x : b) cin >> x;

  n = a.size(), m = b.size();

  ve<ve<int>> store(30, ve<int>(5000));

  for (int i = 0; i < 1 << m; ++i)
  {
    int s = 0;

    for (int j = 0; j < m; ++j)
    {
      if (i >> j & 1) s += b[j];
    }

    ++store[__builtin_popcount(i)][s];
  }

  ll ans = 0;

  for (int i = 0; i < 1 << n; ++i)
  {
    int s = 0;

    for (int j = 0; j < n; ++j)
    {
      if (i >> j & 1) s += a[j];
    }

    const int ppc = __builtin_popcount(i);

    for (int j = 0; j <= m; ++j)
    {
      int cnt = j + ppc;
      int xx = cnt * x;
      if (xx - s >= 0) 
      {
        ans += store[j][xx - s];
      }
    }
  }

  cout << max(ans - 1, 0LL) << ln;
}

int main()
{
  fastio;
  int t = 1; 
  // cin >> t;
  while (t--)
  {
    solve();
  }
  return 0;
}

Submission Info

Judge Result