D - 夕食
Editorial
/
Time Limit: 4 sec / Memory Limit: 128 MB
Problem Statement
2014年春,ある学生は無事大学に合格し,一人暮らしを始める事となった.ここで問題となるのが夕食をどうするかである.彼はこれから $N$ 日間の夕食の計画を立てる事にした.
彼は $N$ 日間で得られる幸福度の合計を出来る限り大きくしたい.もちろん,美味しいものや好きなものを食べるほど幸福度は高い.
彼の夕食の選択肢は2つ,近くの食堂に向かうか,自炊をするかのどちらかである.
食堂で得られる幸福度は,その日のメニューによって変わる.メニューは日替わりだが毎日一種類のみで,$N$ 日間のメニューは全て既に公開されている.なので,彼は $i$ 日目 ($1 \leq i \leq N$) に食堂に行けば $C_i$ の幸福度を得られるという情報を全て知っている.
自炊で得られる幸福度は,その自炊の開始時点での自炊パワーに定数 $P$ を掛けたものである.自炊パワーは初期値が $Q$ であり,毎日,食堂に行けば-1,自炊をすれば+1,その日の食事の終了時に変動する.
彼のために幸福度の総和の最大値を求めよう.
Input
入力は以下の形式で $N+1$ 行で与えられる.
$N$ $P$ $Q$
$C_1$
$C_2$
:
:
$C_N$
- 1行目は3つの整数 $N, P, Q$ が与えられ,それぞれ日数,自炊の幸福度を算出するための定数,自炊パワーの初期値である.
- 2行目から $N+1$ 行目にはそれぞれ整数が1つずつ与えられ,$i+1$ 行目では $i$ 日目に食堂に行った時に得られる幸福度が与えられる.
Constraints
- $1 \leq N \leq 500{,}000$
- $0 \leq P \leq 500{,}000$
- $ |Q| \leq 500{,}000$
- $ | C_i | \leq 500{,}000$
Output
幸福度の取りうる最大値を一行に出力せよ.
Sample Input 1
1 1 1 2
Output for the Sample Input 1
2
- 考えるべき予定は1日だけである.食堂に行けば2,自炊すると1の幸福度なので,答えは2となる.
Sample Input 2
3 2 1 3 3 3
Output for the Sample Input 2
12
- このケースでは毎日自炊をするのが最適で,幸福度は $2 \times 1+2 \times 2+2 \times 3 = 12$となる.
Sample Input 3
3 1 -1 2 -3 2
Output for the Sample Input 3
2
- 2日目のみで自炊をすることが最善となる.
Sample Input 4
3 1 -10 -10 -10 -10
Output for the Sample Input 4
-27
- 答えが負になることもある.いくらまずくても夕食は食べなければならない.