問題一覧 > 通常問題

No.1375 Divide and Update

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 95
作問者 : leaf_1415leaf_1415 / テスター : tempura_pptempura_pp
6 ProblemId : 2766 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-01-31 00:23:03

問題文

$N$ 個の非負整数からなる数列 $a_1, a_2, \ldots, a_N$ が与えられます。
$M=2, 3, 4, \ldots, N-1$ のそれぞれの場合について、以下の【問題】の答えを出力してください。

【問題】
数列 $a$ に対して以下の操作をちょうど $1$ 回行った後の $\sum_{i = 1}^{N} a_i$ としてありうる最大値を答えてください。
(操作)

  1. $1 \leq l_1 \leq r_1 < M < l_2 \leq r_2 \leq N$ を満たす整数 $l_1, r_1, l_2, r_2$ を選択する。
  2. $l_1 \leq i \leq r_1$ を満たすすべての整数 $i$ について、$a_i$ を $X$ に置き換える。
  3. $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もしくは右上の雲マークをクリックしてアカウントを作成してください。