Left Right Operation

题目描述

给定长度为 $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$ 的元素和的最小可能值。

输入格式

输入从标准输入按如下格式给出： $N$ $L$ $R$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出答案。

5 4 3
5 5 0 6 3

14

4 10 10
1 2 3 4

10

10 -5 -3
9 -6 10 -1 2 10 -1 7 -15 5

-58

提示

$1 \leq N \leq 2\times 10^5$ $-10^9 \leq L, R\leq 10^9$ $-10^9 \leq A_i\leq 10^9$ 输入中的所有数值均为整数。如果你选择 $x=2$ 和 $y=2$，你将得到 $A = (4,4,0,3,3)$，其和为 $14$，这是可达到的最小和。
如果你选择 $x=0$ 和 $y=0$，你将得到 $A = (1,2,3,4)$，其和为 $10$，这是可达到的最小和。
$L$、$R$ 和 $A_i$ 可能为负数。

标签: AtCoder|abc263D

来源

AtCoder|abc263D