AtCoder Beginner Contest 184F

ABC184F

解法

半分全列挙． \(a\) を半分に分けて，それぞれの和を集めておき， その vector を \(v_{0}, v_{1}\) とする．
\(x \in v_{0}\) を全探索して， \(y \in v_{1}\) を，\(x + y \leq t\) となるもののうち 最大となる様にとる． これは，前処理で \(v_{1}\) をソートしておけばよい．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n,t;

  cin >> n >> t;

  vll a(n); rep(i,n) { cin >> a[i]; }

 

  ll m = n/2;

  vector<vector<ll>> s(2);

  rep(j,2){

    ll l = 0, r = m;

    if(j==1) l = m, r = n;

    s[j].push_back(0);

    srep(i,l,r) {

      vector<ll> ns;

      for(auto x:s[j]){

        ns.push_back(x);

        if(x+a[i] <= t) ns.push_back(x + a[i]);

      }

      swap(ns,s[j]);

    }

  }

  ll ans = -INFL;

  sort(all(s[1]));

  for(auto x:s[0]){

    auto it = upper_bound(all(s[1]), t-x);

    if(it != s[1].begin()) it--;

    chmax(ans, x + (*it));

  }

  cout << ans << endl;

 

  return 0;

}