問題概要

数列 $a$ の空でない連続する部分列の美しさは $\sum_{i=l}^r a_i$ で決まり、 $N(N+1)/2$ 個存在するすべての部分列から $K$ 個取ってきてそれらの美しさのビット毎の論理積を取った時の最大値を求める。

制約

$2\leq$ $N$ $\leq$ $10^{3}$
$1\leq$ $a_i$ $\leq$ $10^{9}$
$1\leq K \leq N(N+1)/2$
入力はすべて整数

考えたこと

最大値を求めたいのでできるだけ上位のビットを残したいという気持ちにはなる。なので上位のビットからみていき、部分列の美しさのうち今注目しているビットが立っている部分列の美しさが $K$ 個以上あるならばそれらを新たな集合とみなし、次一つ下のビットを見るときには新しい集合に属する値のみについて同じように調べていけばいい。
サンプル１を例に挙げる。部分列全体の集合を $S$ とすると $S=\{2,2,5,5,7,7,7,9,12,14\}$ でありそれぞれ二進数にすると以下のようになる。

美しさ	ビット列
14	0000001110
12	0000001100
9	0000001001
7	0000000111
7	0000000111
7	0000000111
5	0000000101
5	0000000101
2	0000000010
2	0000000010

今下から4ビット目について調べているとすると、4ビット目のビットが立っているのは $\{14,12,9\}$ でありこれを $S'$ とする。 $S'$ は3つの要素からなり、 $K \leq |S'|$ が成り立つので変数ansの下から4ビット目を1にし、次に下から3ビット目を調べるときは集合 $S'$ の要素についてのみ調べればいいことがわかる。