You are given an integer sequence of length $N$: $A=(A_1,A_2,\ldots,A_N)$. You will perform the following consecutive operations just once: Choose an integer $x$ $(0\leq x \leq N)$. If $x$ is $0$, do nothing. If $x$ is $1$ or greater, replace each of $A_1,A_2,\ldots,A_x$ with $L$. Choose an integer $y$ $(0\leq y \leq N)$. If $y$ is $0$, do nothing. If $y$ is $1$ or greater, replace each of $A_{N},A_{N-1},\ldots,A_{N-y+1}$ with $R$. Print the minimum possible sum of the elements of $A$ after the operations.Problem Statement
Constraints
Input
Input is given from Standard Input in the following format:
$N$ $L$ $R$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Print the answer.
Sample Input 1
5 4 3 5 5 0 6 3
Sample Output 1
14
If you choose $x=2$ and $y=2$, you will get $A = (4,4,0,3,3)$, for the sum of $14$, which is the minimum sum achievable.
Sample Input 2
4 10 10 1 2 3 4
Sample Output 2
10
If you choose $x=0$ and $y=0$, you will get $A = (1,2,3,4)$, for the sum of $10$, which is the minimum sum achievable.
Sample Input 3
10 -5 -3 9 -6 10 -1 2 10 -1 7 -15 5
Sample Output 3
-58
$L$, $R$, and $A_i$ may be negative.
设把区间 \([1,l-1]\) 全部变成 \(L\),把区间 \([r+1,n]\) 全部变成 \(R\)，其余不变。预处理出数列 \(a\) 的前缀和 \(s\).
此时的总价值为 $$(s_r-s_{l-1})+L(l-1)+R(n-r)$$
枚举 \(r\)，要找到最大的 \(s_{l-1}-lL\)，在枚举的同时维护最小值就可以了。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,l,r,a[N];
long long s[N],t[N],ans=1e18;
int main()
{
scanf("%d%d%d",&n,&l,&r);
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
s[i]=s[i-1]+a[i];
ans=min(ans,1LL*i*l+1LL*(n-i)*r);
}
ans=min(ans,s[n]);
for(int i=0;i<=n;i++)
t[i]=max(t[i-1],s[i]-1LL*i*l);
for(int i=0;i<=n;i++)
ans=min(ans,s[i]-t[i-1]+1LL*n*r-1LL*i*r);
printf("%lld",ans);
}