E - Both Sides Merger

E - Both Sides Merger

「どちらの操作も全体の合計から自分を引いている」
という事を利用するのかと思ったが、持てる合計を書いてみると最終的な合計に偶数番目と奇数番目が含まれることはないとわかる
また、偶奇上なら自由に選べる

Submission #4267606 - AtCoder Regular Contest 092

void solve() {
    cin >> n;
    na(a, n);
    int bg = -linf;
    int bk = -linf;
    //gu
    int coug = 0;
    int couk = 0;
    int resg = 0;
    int resk = 0;
    rep(i, 0, n, 2) {
        coug += a[i] >= 0;
        if (a[i] >= 0) resg += a[i];
    }
    rep(i, 1, n, 2) {
        couk += a[i] >= 0;
        if (a[i] >= 0) resk += a[i];
    }
    //正の数が2つ以上あれば好きなだけ
    if (coug >= 2) {
        bg = resg;
    } else {
        rep(i, 0, n, 2)chmax(bg, a[i]);
    }
    if (couk >= 2) {
        bk = resk;
    } else {
        rep(i, 1, n, 2)chmax(bk, a[i]);
    }
    vi ind;
    if (bg >= bk) {
        cout << bg << endl;
        if (coug >= 2) {
            rep(i, 0, n, 2)if (a[i] >= 0)ind += i;
        } else {
            int mai = 0;
            int mag = -linf;
            rep(i, 0, n, 2)if (mag < a[i])mag = a[i], mai = i;
            ind += mai;
        }
    } else {
        cout << bk << endl;
        if (couk >= 2) {
            rep(i, 1, n, 2)if (a[i] >= 0) ind += i;
        } else {
            int mai = 0;
            int mak = -linf;
            rep(i, 1, n, 2)if (mak < a[i])mak = a[i], mai = i;
            ind += mai;
        }
    }
    vi sou;
    int in = sz(ind);
    rep(i, n - (ind[in - 1] + 1))sou += n - i;
    rep(i, ind[0])sou += 1;
    rep(i, sz(ind) - 1) {
        rep(j, (ind[i + 1] - ind[i]) / 2 - 1)sou += 1 + 2;
        sou += 1 + 1;
    }
    cout << sz(sou) << endl;
    for (auto &&v :sou)cout << v << endl;
}