Bình luận

• 
  

  -4

  kingofgame    12:25 a.m. 29 Tháng 5, 2024

  include <bits/stdc++.h>

  define el '\n'

  define fu(i, a, b) for(long long i = a; i <= b; ++i)

  define fd(i, a, b) for(long long i = a; i >= b; --i)

  define ff first

  define ss second

  define all(v) v.begin(), v.end()

  define mask(i) (1LL << (i))

  define bit(x, i) (((x) >> (i)) & 1)

  define sz(v) (ll) v.size()

  using namespace std;
  using ll = long long;
  using ull = unsigned long long;
  const long long N = 21, mod = 1e9 + 7, base = 29, inf = 1e18;
  mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
  ll Rand(ll l, ll r) {
  return uniform_int_distribution<ll> (l, r) (rng);
  }
  ll last(ll msk) {
  return msk & (-msk);
  }
  ll pop_cnt(ll msk) {
  return __builtin_popcountll(msk);
  }
  ll ctz(ll msk) {
  return __builtin_ctzll(msk);
  }
  ll lg(ll msk) {
  return 63 - __builtin_clzll(msk);
  }
  template <class T1, class T2>
  bool minimize(T1 &a, T2 b) {
  if (a > b) {
  a = b;
  return true;
  }
  return false;
  }
  template <class T1, class T2>
  bool maximize(T1 &a, T2 b) {
  if (a < b) {
  a = b;
  return true;
  }
  return false;
  }
  template <class T>
  void print(T a) {
  for (auto x : a) cout << x << " ";
  cout << el;
  }
  template <class T>
  void compress(vector<T> &a) {
  sort(all(a));
  a.resize(unique(all(a)) - a.begin());
  }
  ll n, x;
  ll a[N];
  pair<ll, ll> f[mask(N)];
  signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> x;
  fu(i, 0, n - 1) cin >> a[i];
  memset(f, 0x3f, sizeof(f));
  f[0] = {1, 0};
  fu(msk, 0, mask(n) - 1) {
  ll leftover = (mask(n) - 1) ^ msk;
  for (ll tmp = leftover; tmp > 0; tmp ^= last(tmp)) {
  ll i = ctz(tmp);
  ll newMsk = msk ^ mask(i);
  if (f[msk].ss + a[i] <= x) {
  if (f[newMsk].ff > f[msk].ff) {
  f[newMsk].ff = f[msk].ff;
  f[newMsk].ss = f[msk].ss + a[i];
  }
  else if (f[newMsk].ff == f[msk].ff) {
  minimize(f[newMsk].ss, f[msk].ss + a[i]);
  }
  }
  else {
  if (f[newMsk].ff > f[msk].ff + 1) {
  f[newMsk].ff = f[msk].ff + 1;
  f[newMsk].ss = a[i];
  }
  else if (f[newMsk].ff == f[msk].ff + 1) {
  minimize(f[newMsk].ss, a[i]);
  }

          }
      }
  }
  cout << f[mask(n) - 1].ff;
  

  }