102633: [AtCoder]ABC263 D - Left Right Operation
Description
Score : $400$ points
Problem Statement
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.
Constraints
- $1 \leq N \leq 2\times 10^5$
- $-10^9 \leq L, R\leq 10^9$
- $-10^9 \leq A_i\leq 10^9$
- All values in input are integers.
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.
Input
题意翻译
有一个长度为 N 的数列 A={$a_1$,$a_2$,$a_3$...$a_n$}. * 选择一个整数 X (0 $\le$X$\le$N) , 如果 X 选0，则不做任何操作，否则用 L 替换 $a_1$,$a_2$,$a_3$...$a_X$. * 选择一个整数 Y (0 $\le$Y$\le$N) ，如果 Y 选0，则不做任何操作，否则用R替换 $a_N$,$a_{N-1}$,$a_{N-2}$...$a_{N-Y+1}$ . 求操作后 A 数列总和的最小值。Output
分数：400分
问题描述
给你一个长度为$N$的整数序列$A=(A_1,A_2,\ldots,A_N)$。
你只需执行一次以下连续操作：
-
选择一个整数$x$ $(0\leq x \leq N)$。如果$x$为0，则不做任何操作。如果$x$为1或更大，则将$A_1,A_2,\ldots,A_x$替换为$L$。
-
选择一个整数$y$ $(0\leq y \leq N)$。如果$y$为0，则不做任何操作。如果$y$为1或更大，则将$A_{N},A_{N-1},\ldots,A_{N-y+1}$替换为$R$。
输出操作后$A$的元素和的最小值。
限制条件
- $1 \leq N \leq 2\times 10^5$
- $-10^9 \leq L, R\leq 10^9$
- $-10^9 \leq A_i\leq 10^9$
- 输入中的所有值都是整数。
输入
输入从标准输入中给出以下格式：
$N$ $L$ $R$ $A_1$ $A_2$ $\ldots$ $A_N$
输出
输出答案。
样例输入1
5 4 3 5 5 0 6 3
样例输出1
14
如果选择$x=2$和$y=2$，你将得到$A = (4,4,0,3,3)$，元素和为14，这是可以达到的最小和。
样例输入2
4 10 10 1 2 3 4
样例输出2
10
如果选择$x=0$和$y=0$，你将得到$A = (1,2,3,4)$，元素和为10，这是可以达到的最小和。
样例输入3
10 -5 -3 9 -6 10 -1 2 10 -1 7 -15 5
样例输出3
-58
$L$，$R$和$A_i$可能为负数。