C - ADD MUL MAX
問題文
$N$ 個のボールがあり、それぞれ $1, 2, \ldots ,N$ と番号が付けられています。
番号 $i$ のボールには整数 $A_i$ が書かれています。
あなたは以下の 2 種類の操作を高々 1 回ずつ行います。
ただし、2 種類の操作を両方行う場合、必ず操作 1 を行った後に操作 2 を行うものとします。
操作後の全てのボールに書かれている整数の合計の最大値を求めてください。
操作 1
整数 $l, r \space (1 \leq l \leq r \leq N)$ を選び、$i=l,l+1, \ldots ,r$ の順に以下の変更を行う。
- 番号 $i$ のボールに書かれている整数に、$X$ を加える。
操作 2
整数 $l, r \space (1 \leq l \leq r \leq N)$ を選び、$i=l,l+1, \ldots ,r$ の順に以下の変更を行う。
- 番号 $i$ のボールに書かれている整数に、$Y$ をかける。
制約
- 入力は全て整数
- $1 \leq N \leq 2 \times 10^5$
- $-10^5 \leq X, Y \leq 10^5$
- $-10^5 \leq A_i \leq 10^5$
部分点
この問題には部分点が設定されています。
- $Y > 0$ を満たすデータセットに正解した場合には、$200$ 点が与えられます。
入力
$N$ $X$ $Y$
$A_1 \space A_2 \space \ldots \space A_N$
出力
答えを1行に出力してください。
5 3 2
1 2 3 4 5
60
初めに、整数 $l=1,r=5$ を選んで操作 1 を行います。
操作後のボールに書かれている整数は、番号 $i=1,2, \ldots ,N$ の順に $4,5,6,7,8$ となります。
次に、整数 $l=1,r=5$ を選んで操作 2 を行います。
操作後のボールに書かれている整数は、番号 $i=1,2, \ldots ,N$ の順に $8,10,12,14,16$ となります。
全ての操作を終えた後、ボールに書かれている整数の合計は $8+10+12+14+16=60$ です。
合計が $60$ より大きくなるような操作の仕方は存在しないため、答えとして $60$ を出力します。
また、このケースは部分点制約を満たします。
5 1 -2
1 -2 3 -4 5
18
初めに、整数 $l=1,r=3$ を選んで操作 1 を行います。
操作後のボールに書かれている整数は、番号 $i=1,2, \ldots ,N$ の順に $2,-1,4,-4,5$ となります。
次に、整数 $l=4,r=4$ を選んで操作 2 を行います。
操作後のボールに書かれている整数は、番号 $i=1,2, \ldots ,N$ の順に $2,-1,4,8,5$ となります。
全ての操作を終えた後、ボールに書かれている整数の合計は $2+(-1)+4+8+5=18$ です。
合計が $18$ より大きくなるような操作の仕方は存在しないため、答えとして $18$ を出力します。
操作 2 を行った後に操作 1 を行うことは出来ないことに注意してください。
このケースは部分点制約を満たしません。
5 1 -2
1 2 3 4 5
20
初めに、整数 $l=1,r=5$ を選んで操作 1 を行います。
操作後のボールに書かれている整数は、番号 $i=1,2, \ldots ,N$ の順に $2,3,4,5,6$ となります。
操作 2 は行わないことにします。
全ての操作を終えた後、ボールに書かれている整数の合計は $2+3+4+5+6=20$ です。
合計が $20$ より大きくなるような操作の仕方は存在しないため、答えとして $20$ を出力します。
このケースは部分点制約を満たしません。