てん vs. ほむ [yukicoder 999]

https://yukicoder.me/problems/no/999

解説

https://yukicoder.me/submissions/436467

ルールを整理してみると、最終的な選択は以下のようになる。
「ほ」はほむらちゃん、「て」はてんぷらくん。
ほてほてほて てほてほ
このように、左をとるとほてと取れて、右をとるとてほととれる。
つまり、ほての連続 + てほの連続のような選択になる。
ほむらちゃんが選択すれば、てんぷらくんの選択は一意に定まるので、ほむらちゃんの操作回数のみを考える。
左をk回とると、右はN-k回とることになる。
これをうまく全探索することで答えを導こう。

差分を計算することで、うまく計算する。
まずは、てほてほてほ…で合計値を計算しよう。
先頭からてほになっている所を打ち消して、ほてと選択を変えながら、全体のコストを差分を使って計算しよう。
累積和を使うことで、左を何回とるかを全探索して、計算することもできる。

int N, A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N * 2) cin >> A[i];

    ll ans = -infl;
    ll tot = 0;
    rep(i, 0, N * 2) {
        if (i % 2 == 0) tot -= A[i];
        else tot += A[i];
    }
    chmax(ans, tot);
    rep(i, 0, N) {
        int first = A[i * 2];
        int second = A[i * 2 + 1];

        tot = tot + first - second; // 打消し
        tot = tot + first - second; // ほてにする
        chmax(ans, tot);
    }
    cout << ans << endl;
}