[AtCoder] ABC 182 D – Wandering

2020年11月9日2020年12月12日

問題

方針

\( A \) の累積和を \( b \) とし、\( b \) の累積和を \( c \) とすると、

\begin{eqnarray}
b_i &=& A_1 + A_2 + \cdots + A_i\\
c_i &=& b_1 +b_1 + \cdots + b_i
\end{eqnarray}

となります。ここで、ロボットの移動距離を、\( c_i + x_i \ (0 \leq x_i \leq c_{i})\) と表します。\( x_i \) の値は連続値ではなく離散値となることに注意します。\( c_i + x_i \) を最大化する \( x_i \) は、\( A_1 \) から\( A_{i} \) までの累積和の最大値なので、あらかじめ累積和の最大値を計算しておき、\( c_i + x_i \) を全探索します。また、\( x_N = 0 \) です。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int N;
    cin >> N;
    ll A[N];
    ll b[N + 1]{};
    ll c[N + 1]{};
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        b[i + 1] = b[i] + A[i];
    }
    for (int i = 0; i < N; i++) {
        c[i + 1] = c[i] + b[i + 1];
    }
    ll v[N + 1]{};
    ll sum = 0;
    for (int i = 0; i < N; i++) {
        sum += A[i];
        v[i + 1] = max(v[i], sum);
    }
    ll best = 0;
    for (int i = 1; i < N; i++) {
        best = max(best, c[i] + v[i]);
    }
    best = max(best, c[N]);
    cout << best << "\n";
    return 0;
}