AtCoder ABC095 D

April 28, 2020

https://atcoder.jp/contests/abc095/tasks/arc096_b

$S = \text{摂取カロリーの総和} - \text{消費カロリー}$ を最大化したい。

動かないで寿司屋をでると $S = 0$ なので $S \ge 0$ が成り立つ
左(右)回りに移動して途中の寿司を食べずにその先の寿司を食べることは、途中の寿司を食べる場合より明らかにSは小さくなるので、そういう動き方はできないというルールに変えても問題はない
左に動いて寿司1を食べて、戻って右に動いて寿司2を食べて、また戻って左に動いて寿司3を食べるという動きは、最初に寿司1,3を食べて戻って寿司2を食べるという動きより明らかに消費カロリーが増える

これらを踏まえると、結局動き方としては、左回りにL個食べて、戻って右回りにR個食べる( $L + R \le N$ )、あるいは、右回りにR個、戻って左回りにR個食べるのどちらか(左回りにL(右回りにR)個食べて寿司屋を出る場合も考慮する)。

L, Rのすべての組み合わせについてSを計算すると $O(N^2)$ なので今回の制約では間に合わない。そこで、Lを固定したときにSを最大化するRを効率よく求めたい。

左回りにL個食べたとき、戻って右回りに食べられる個数は $N - L$ 個なので、最初の位置から右回りに $R \le N - L$ 個食べたときのSの最大値を事前に求めておけばいい。これは単純なdpで計算できる。

実装

int main() {
    i64 N, C; cin >> N >> C;
    vector<i64> CX(N + 1, 0);
    vector<i64> V(N);
    REP(i, N) cin >> CX[i + 1] >> V[i];

    vector<i64> CV(N + 1, 0);
    REP(i, N) CV[i + 1] = CV[i] + V[i];

    vector<i64> dp(N + 1, 0);
    REP(i, N) {
        chmax(dp[i + 1], dp[i]);
        chmax(dp[i + 1], (CV[N] - CV[N - i - 1]) - (C - CX[N - i]));
    }

    i64 maxv = 0;

    REP(l, N) {
        i64 v = CV[l + 1] - CX[l + 1];
        chmax(maxv, v);
        v -= CX[l + 1];
        chmax(maxv, v + dp[N - (l + 1)]);
    }

    REP(i, N + 1) dp[i] = 0;
    REP(i, N) {
        chmax(dp[i + 1], dp[i]);
        chmax(dp[i + 1], CV[i + 1] - CX[i + 1]);
    }
    REP(r, N) {
        i64 v = (CV[N] - CV[N - r - 1]) - (C - CX[N - r]);
        chmax(maxv, v);
        v -= C - CX[N - r];
        chmax(maxv, v + dp[N - (r + 1)]);
    }

    cout << maxv << endl;

    return 0;
}