前提知識

Wavelet Matrix

解説

何から考えたものかという感じだが、Kを全探索しよう。
あるKについて、全て左端からK人グループを作っていくと、N/K回操作を行うことになる。
この時点で計算量は調和級数的計算量でO(NlogN)
よって、
- 左端からi回操作をしたときの行動力の総和をlft[i]
- 右端からi回操作をしたときの行動力の総和をrht[i]
として前計算しておけば、lft[i]を全探索して、区間がかぶらないようなrht[i]の最大値との和を考えていけばいい。
これはlft[i]をiが大きい順から見ていけば、区間がかぶらないようなrht[i]は単調増加していくので、
maxを取りながら見ていくことができ、O(N/K)でできる。
よって、全てのKについて、全てのグループの作り方を試してもO(NlogN)に収まる。

あと問題になるのは、ある区間についてK/2番目、(K+1)/2番目に大きい数を求めたいという部分。
これについてはやり方が色々ある。
WaveletMatrixでできる。
自分はWMは全然理解してないので、antaさんのライブラリを拝借すると爆速で通る。
最近始めた人は知らないかもしれないが、antaさんというのはデータ構造神。

int N, A[10101];
ll lft[10101], rht[10101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    vector<int> A;
    rep(i, 0, N) {
        int x; cin >> x;
        A.push_back(x + inf);
    }

    AntaWaveletMatrixWrapper wm;
    wm.init(A);

    ll ans = 0;
    rep(K, 1, N + 1) {
        int kth = (K + 1) / 2 - 1;

        lft[0] = 0;
        rep(st, 0, N / K) lft[st + 1] = lft[st] + wm.kth_number(st * K, (st + 1) * K, kth) - inf;

        rht[0] = 0;
        rep(st, 0, N / K) rht[st + 1] = rht[st] + wm.kth_number(N - (st + 1) * K, N - st * K, kth) - inf;

        ll ma = 0;
        int rh = 1;
        rrep(lf, N / K, 0) {
            chmax(ans, (lft[lf] + ma) * K);
            chmax(ma, rht[rh]);
            rh++;
        }
    }
    cout << ans << endl;
}

はまやんはまやんはまやん

hamayanhamayan's blog

You Are A Project Manager [yukicoder 919]

前提知識

解説