Submission #18345306

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll N; cin >> N;
  ll T; cin >> T;
  vector<ll> A(N); for (ll i = 0; i < N; i++) cin >> A[i];

  set<ll> st1, st2;
  ll m1 = N / 2, m2 = N - m1;
  st1.insert(0);
  st2.insert(0);
  for (ll i = 0; i < (1 << m1); i++) {
    ll temp = 0;
    for (ll j = 0; j < m1; j++) {
      if ((i>>j) & 1) temp += A[j];
    }
    st1.insert(temp);
  }
  for (ll i = 0; i < (1 << m2); i++) {
    ll temp = 0;
    for (ll j = 0; j < m2; j++) {
      if ((i>>j) & 1) temp -= A[m1 + j];
    }
    st2.insert(temp);
  }

// for (auto itr = st1.begin(); itr != st1.end(); ++itr) {
//   cout << *itr << "\n";
// }
// for (auto itr = st2.begin(); itr != st2.end(); ++itr) {
//   cout << *itr << "\n";
// }

  ll ans = 0;
  for (auto itr = st1.begin(); itr != st1.end(); ++itr) {
    ll temp = *itr;
    if (temp > T) continue;
    auto itr2 = st2.lower_bound(temp - T);
    // auto itr2 = lower_bound(st2.begin(), st2.end(), T - temp);
    ll l = *itr2;
    if (temp - l <= T) {
      ans = max(ans, temp - l);
    }
  }

  cout << ans << '\n';
  return 0;
}

Submission Info

Judge Result