No.409 ダイエット

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 27
作問者 : btkbtk / テスター : cielciel

4 ProblemId : 1064 / 出題時の順位表

問題文

btkさんは毎日ドーナツを食べています.
ある日,btkさんは N 日間ダイエットをすることを決意しました.
btkさんは毎日違うお店でドーナツを買っていて,ダイエット開始から i 日目に訪れるお店でドーナツを食べると$D_i$kg体重が増えることが分かっています. また,1 日ドーナツを食べるのをやめると,$A$kg痩せることができます.

しかし,ドーナツを食べない日が続くとストレスが溜まります.ここで,ストレス値というパラメータを定義します. ダイエット開始時点でのストレス値は0です.
1 日ドーナツを食べないとストレス値が 1 溜まり,1日の終了時にbtkさんの体重は$B*(ストレス値)$kg増加します. ドーナツを食べるとストレス値は 0 に戻ります.

各日において,ストレス値の変化後に体重が変化することに注意してください.

ダイエット開始前のbtkさんの体重を $W$ kgとしたとき,N 日間で何kgに痩せることができるでしょうか.

入力

$N$ $A$ $B$ $W$
$D_1$ $D_2$ ... $D_{N}$

$1 \le N \le 3*10^5$
$0 \le A,B,W \le 10^6$
$0 \le D_i \le 10^6$

出力

N日目終了後のbtkさんの体重の最小値を1行で出力してください.
終了時の体重はマイナスになることもあります.

サンプル

サンプル1
入力
2 5 2 10
0 6
出力
6

2日ともドーナツを食べた場合
$10 + (0) + (6) = 16$
1日目のみドーナツを食べた場合
$10 + (0) + (-5 + 2×1)=7$
2日目のみドーナツを食べた場合
$10 + (-5 + 2×1) + (6) = 13$
2日ともドーナツを食べなかった場合
$10 + (-5 + 2×1) + (-5 + 2×2) = 6$

よって,2日ともドーナツを食べなかった場合が最適となり,答えは6となります.

サンプル2
入力
5 1 0 50
1 2 3 4 5
出力
45

btkさんはストレス太りしないので5日間断食をするのが最適になります.

サンプル3
入力
7 4 6 56
10 9 7 17 8 3 7
出力
88

どのように頑張っても体重が減ることはありません(血涙)

提出ページヘ