Sum AND Subarrays [Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選 B]

https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_b

解説

https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3660039

まず、空でない連続する部分列は全列挙可能なのでやる。
本当に愚直にやるとO(N^3)掛かるが、ある区間[L,R]の総和は累積和を用いるとO(1)にできるので、
O(N^2)で実現できる。
全列挙した部分列の総和を配列vに入れておく。
　
次に、AND和の最大値を考えるが、ビットごとに考えていこう。
貪欲な解法を考えると、上位のビットほど1になっている方が数が大きくなる。
ok[i] := その数を用いるとここまで確定しているビットを実現できるか
という配列を用意し、全てtrue（=1）として初期化しておこう。
これを使って、上位のビットから貪欲に決めていく。
　
貪欲の内容は、「ok[i]=1」かつ「決めたい桁のビットが1」である数の個数がK以上であれば、
それらのいずれかを使って実現できるので、その場合に決めたい桁のビットを1にして、
決めたい桁のビットが1でない数のokを0にする。
これを順番にやっていくと、答えが求まる。

int N, K; ll A[1010];
ll sm[1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];
 
    sm[0] = A[0];
    rep(i, 1, N) sm[i] = sm[i - 1] + A[i];
 
    vector<ll> v;
    rep(l, 0, N) rep(r, l, N) {
        ll tot = sm[r];
        if (l) tot -= sm[l - 1];
        v.push_back(tot);
    }
    int n = v.size();
    vector<int> ok(n, 1);
 
    ll ans = 0;
    rrep(d, 60, 0) {
        ll msk = 1LL << d;
        int cnt = 0;
        rep(i, 0, n) if (v[i] & msk and ok[i]) cnt++;
        if (K <= cnt) {
            ans += msk;
            rep(i, 0, n) if (!(v[i] & msk) and ok[i]) ok[i] = 0;
        }
    }
 
    cout << ans << endl;
}