[AtCoder] ABC 182 D – Wandering

問題

方針

\( 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 \) です。

コード