問題一覧 > 通常問題

No.1375 Divide and Update

レベル : / AI推定難易度 : 1100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 123
作問者 : leaf_1415 / テスター : tempura_pp
お気に入りにしたユーザー ProblemId : 2766 / 自分の提出
問題文最終更新日: 2021-01-31 00:23:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 281 (順位表) の他の問題:

Problem Statement

You are given a sequence $a_1, a_2, \ldots, a_N$ consisting of $N$ non-negative integers.
For each of the cases $M=2, 3, 4, \ldots, N-1$, output the answer to the following [Problem].

[Problem]
Find the maximum possible value of $\sum_{i = 1}^{N} a_i$ after performing the following operation on the sequence $a$ exactly $1$ time.
(Operation)

  1. Choose integers $l_1, r_1, l_2, r_2$ satisfying $1 \leq l_1 \leq r_1 < M < l_2 \leq r_2 \leq N$.
  2. For every integer $i$ satisfying $l_1 \leq i \leq r_1$, replace $a_i$ with $X$.
  3. For every integer $i$ satisfying $l_2 \leq i \leq r_2$, replace $a_i$ with $Y$.

Input

$N\ X\ Y$
$a_1\ a_2\ \ldots\ a_N$

The input satisfies the following constraints.
$3 \leq N \leq 2 \times 10^5$
$0 \leq X, Y \leq 10^9$
$0 \leq a_i \leq 10^9$
All input values are integers.

Output

Output $N-2$ lines.
On the $i$-th line $(1 \leq i \leq N-2)$, output the answer to the [Problem] for $M = i+1$.
Print a newline at the end.

Sample

Sample 1
Input
7 5 6
4 2 9 3 7 1 6
Output
40
43
41
41
36

When $M=2$, choosing $(l_1, r_1) = (1, 1),\ (l_2, r_2) = (4, 6)$ turns
the sequence $a$ into $(5, 2, 9, 6, 6, 6, 6)$, and $\sum_{i = 1}^{N} a_i = 40$ is the maximum.

When $M=3$, choosing $(l_1, r_1) = (1, 2),\ (l_2, r_2) = (4, 6)$ turns
the sequence $a$ into $(5, 5, 9, 6, 6, 6, 6)$, and $\sum_{i = 1}^{N} a_i = 43$ is the maximum.

When $M=4$, choosing $(l_1, r_1) = (1, 2),\ (l_2, r_2) = (6, 6)$ turns
the sequence $a$ into $(5, 5, 9, 3, 7, 6, 6)$, and $\sum_{i = 1}^{N} a_i = 41$ is the maximum.

When $M=5$, choosing $(l_1, r_1) = (1, 2),\ (l_2, r_2) = (6, 6)$ turns
the sequence $a$ into $(5, 5, 9, 3, 7, 6, 6)$, and $\sum_{i = 1}^{N} a_i = 41$ is the maximum.

When $M=6$, choosing $(l_1, r_1) = (1, 2),\ (l_2, r_2) = (7, 7)$ turns
the sequence $a$ into $(5, 5, 9, 3, 7, 1, 6)$, and $\sum_{i = 1}^{N} a_i = 36$ is the maximum.

Sample 2
Input
12 4 7
3 1 4 1 5 9 2 6 5 3 5 8
Output
76
76
70
73
73
68
67
65
61
58

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。