No.1375 Divide and Update
タグ : / 解いたユーザー数 117
作問者 :
leaf_1415
/ テスター :
tempura_pp
問題文
$N$ 個の非負整数からなる数列 $a_1, a_2, \ldots, a_N$ が与えられます。
$M=2, 3, 4, \ldots, N-1$ のそれぞれの場合について、以下の【問題】の答えを出力してください。
【問題】
数列 $a$ に対して以下の操作をちょうど $1$ 回行った後の $\sum_{i = 1}^{N} a_i$ としてありうる最大値を答えてください。
(操作)
- $1 \leq l_1 \leq r_1 < M < l_2 \leq r_2 \leq N$ を満たす整数 $l_1, r_1, l_2, r_2$ を選択する。
- $l_1 \leq i \leq r_1$ を満たすすべての整数 $i$ について、$a_i$ を $X$ に置き換える。
- $l_2 \leq i \leq r_2$ を満たすすべての整数 $i$ について、$a_i$ を $Y$ に置き換える。
入力
$N\ X\ Y$ $a_1\ a_2\ \ldots\ a_N$
入力は以下の制約を満たします。
$3 \leq N \leq 2 \times 10^5$
$0 \leq X, Y \leq 10^9$
$0 \leq a_i \leq 10^9$
入力値はすべて整数
出力
出力は $N-2$ 行にわたります。
$i$ 行目 $(1 \leq i \leq N-2)$ には、$M = i+1$ としたときの【問題】の答えを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
7 5 6 4 2 9 3 7 1 6
出力
40 43 41 41 36
$M=2$ のとき、$(l_1, r_1) = (1, 1),\ (l_2, r_2) = (4, 6)$ とすると、
数列 $a$ は $(5, 2, 9, 6, 6, 6, 6)$ になり、$\sum_{i = 1}^{N} a_i = 40$ で最大です。
$M=3$ のとき、$(l_1, r_1) = (1, 2),\ (l_2, r_2) = (4, 6)$ とすると、
数列 $a$ は $(5, 5, 9, 6, 6, 6, 6)$ になり、$\sum_{i = 1}^{N} a_i = 43$ で最大です。
$M=4$ のとき、$(l_1, r_1) = (1, 2),\ (l_2, r_2) = (6, 6)$ とすると、
数列 $a$ は $(5, 5, 9, 3, 7, 6, 6)$ になり、$\sum_{i = 1}^{N} a_i = 41$ で最大です。
$M=5$ のとき、$(l_1, r_1) = (1, 2),\ (l_2, r_2) = (6, 6)$ とすると、
数列 $a$ は $(5, 5, 9, 3, 7, 6, 6)$ になり、$\sum_{i = 1}^{N} a_i = 41$ で最大です。
$M=6$ のとき、$(l_1, r_1) = (1, 2),\ (l_2, r_2) = (7, 7)$ とすると、
数列 $a$ は $(5, 5, 9, 3, 7, 1, 6)$ になり、$\sum_{i = 1}^{N} a_i = 36$ で最大です。
サンプル2
入力
12 4 7 3 1 4 1 5 9 2 6 5 3 5 8
出力
76 76 70 73 73 68 67 65 61 58
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。