解法1：式変形
考え方
愚直に計算する方法を考えて，そのあと計算量を落とすことができるか検討する．$x, y$を全探索すると
\begin{aligned}
f(x, y) = Lx + \sum_{k = x + 1}^{N - y} A_{k} + yR
\end{aligned}
の最小値を計算できる（この表式は，$x = 0$，$y = 0$のときも正しい）．f(x, y) = Lx + \sum_{k = x + 1}^{N - y} A_{k} + yR
\end{aligned}
2項目の和は，累積和を使うと計算量を落とせる．つまり，
\begin{aligned}
\mathrm{acc}[0]
&= 0 \\
\mathrm{acc}[n]
& = \sum_{k = 1}^{n} A_{k}
\end{aligned}
を予め計算しておけば\mathrm{acc}[0]
&= 0 \\
\mathrm{acc}[n]
& = \sum_{k = 1}^{n} A_{k}
\end{aligned}
\begin{aligned}
\sum_{k = x + 1}^{N - y} A_{k}
&= \mathrm{acc}[N - y] - \mathrm{acc}[x]
\end{aligned}
と$O(1)$で計算できる．\sum_{k = x + 1}^{N - y} A_{k}
&= \mathrm{acc}[N - y] - \mathrm{acc}[x]
\end{aligned}
これを$f(x, y)$に代入すれば，変数$x$の項と変数$y$の項を分離できる．
\begin{aligned}
f(x, y)
& = (Lx - \mathrm{acc}[x]) + (\mathrm{acc}[N - y] + yR).
\end{aligned}
f(x, y)
& = (Lx - \mathrm{acc}[x]) + (\mathrm{acc}[N - y] + yR).
\end{aligned}
あとは，$0\leq x + y \leq N$に注意して最小値が求められれば良い．これは，各$0 \leq i \leq N$に対して「累積min」
\begin{aligned}
g_{1} (i) &= \min_{x \leq i} (Lx - \mathrm{acc}[x]) \\
g_{2} (i) &= \min_{y \leq i} (\mathrm{acc}[N - y] + yR)
\end{aligned}
を$O(N)$で計算しておくことで，g_{1} (i) &= \min_{x \leq i} (Lx - \mathrm{acc}[x]) \\
g_{2} (i) &= \min_{y \leq i} (\mathrm{acc}[N - y] + yR)
\end{aligned}
\begin{aligned}
\min_{0\leq i \leq N} [g_{1} (i) + g_{2} (N - i) ]
\end{aligned}
と$O(N)$で計算できる．\min_{0\leq i \leq N} [g_{1} (i) + g_{2} (N - i) ]
\end{aligned}
回答例
N, L, R = map(int, input().split()) A = list(map(int, input().split())) acc = [0] * (N + 1) for i in range(N): acc[i + 1] = acc[i] + A[i] acc_min_x = [0] * (N + 1) for i in range(1, N + 1): acc_min_x[i] = min(acc_min_x[i - 1], L * i - acc[i]) acc_min_y = [0] * (N + 1) acc_min_y[0] = acc[N] for i in range(1, N + 1): acc_min_y[i] = min(acc_min_y[i - 1], acc[N - i] + i * R) ans = sum(A) for i in range(N + 1): ans = min(ans, acc_min_x[i] + acc_min_y[N - i]) print(ans)
