https://emtubasa.hateblo.jp/entry/2019/02/03/224024

解法

2進数の桁DPです。
$dp[i][j][k]$ としたとき、 $i$ は現在見ている桁を表し、下から $i+1$ 桁目、 $j$ は $i$ 桁目で0を使うか1を使うか、 $k$ は桁DPで毎回出てくる、 $K$ 以下が確定しているかどうか、です。
今回は、 $i$ が大きい方から見ていきます。そして、現時点での答え、すなわち最大値を格納していきます。
答えは $dp[0][j][k]$ です。
前計算として、 $N$ 個の数字 $A$ について、 $i$ 桁目が1である個数を計算しておきます。これを $c_{i}$ とします。
遷移をざっと書きます。
$K$ の $i$ 桁目が $1$ だった場合
$dp[i][0][1] = max(dp[i+1][j][k]) +c_{i} \times 2^{i}$
$dp[i][1][k] = max(dp[i+1][j][k]) + (N-c_{i})\times 2^{i}$
となります。対して、
$K$ の $i$ 桁目が $0$ だった場合
$dp[i][0][k] = max(dp[i+1][j][k]) + c_{i} \times 2^{i}$
$dp[i][1][1] = max(dp[i+1][j][1]) + (N-c_{i}) \times 2^{i}$
です。ここで、注意すべき点がいくつかあります。
まず、DPを開始する地点です。 $K$ より大きい最小の $2^{i}$ ではなく、 $A$ と $K$ の最大値より大きい、最小の $2^{i}$ になります。これはサンプルの3でわかります。
そして、これにより、 $K$ の $i$ 桁目が $1$ だった場合の $dp[i][1][1]$ は、DPの開始直後の $i$ だった場合は計算してはいけません。同様に、 $K$ の $i$ 桁目が $0$ だった場合も、 $2^{i} \leqq K$ でないと、 $dp[i][j][1]$ の遷移を行ってはいけません。どちらのパターンも、まだ $K$ 以下とは確定していないからです。
あとは、このDPを計算すれば、答えを求めることができます。