ABC184 F - Programming Contest (600)
問題の選び方は$ 2^N通り存在し、これらを全て試すのは$ O(2^N N)で間に合わない
問題を左半分と右半分のグループに分割する
右半分のグループはそのグループ内の和としてあり得る全ての和を求めておく
左半分のグループではそのグループ内の和それぞれに対して、右半分のグループの和と足して条件を満たせる最大の値を二分探索する
全ての左半分のグループでの和に対しての中での最大値が答え
右半分のグループの和を全て求めるのが$ O(2^{\frac{N}{2}} N)
左半分のグループでの和を求めるのが$ O(N)、それに対して二分探索するのが$ O(N)で全体で$ O(2^{\frac{N}{2}} N)