No.2659 Manga App
タグ : / 解いたユーザー数 6
作問者 :
hamamu
/ テスター :
nok0
てんぷら
問題文
hamamuさんは漫画アプリで第 $1$ 話から第 $N$ 話まで読破しようとしています。
有効な表示ボタン $i$ を押すと第 $i$ 話が読めるようになりますが、
時刻 $0$ では表示ボタン $1$ のみ有効で他は無効になっています。
無効な表示ボタンは押すことができません。
表示ボタン $i (1 \le i \le N - 1)$ を時刻 $t$ に押すと、
表示ボタン $i + 1$ の「有効化時刻」が $t + A_i$ にセットされます。
表示ボタン $i + 1$ の有効化時刻になると表示ボタン $i + 1$ が有効になります。
hamamuさんは $B$ 時間起きて $C$ 時間寝る生活をしており、 寝ているときは表示ボタンを押せません。 正確に書くと以下のとおりです。
- $D = B + C, k = 0, 1, \cdots$ とする
- 時刻 $t$ が $kD \le t \le kD + B$ のとき起きている
- 時刻 $t$ が $kD + B \lt t \lt (k + 1)D$ のとき寝ていて表示ボタンを押せない
漫画アプリには「時短アイテム」があり、hamamuさんは時短アイテムを $X$ 個持っています。
時短アイテムを1つ消費したときの効果は以下のとおりです。
最後に押したのが表示ボタン $i$ で、
表示ボタン $i + 1$ がまだ有効になっていないとき、
表示ボタン $i + 1$ の有効化時刻が $1$ 減る（早まる）
時短アイテムは、起きていればいつでも、連続して何個でも消費できます。
また、時短アイテム消費にかかる時間、
表示ボタン押下にかかる時間は非常に短く、無視できるものとします。
hamamuさんは時刻 $0$ に表示ボタン $1$ を押しました。
表示ボタン $N$ を押して第 $N$ 話を読めるようにするまでにかかる時間が
最短になるように行動したとき、
第 $N$ 話が読めるようになる時刻を求めてください。
制約
- 入力はすべて整数
- $2 \le N \le 2000$
- $1 \le B \le 10^9$
- $2 \le C \le 10^9$
- $0 \le X \le 10^{10}$
- $1 \le A_i \le 10^9$
入力
以下の形式で標準入力から与えられます。$N\ B\ C\ X$
$A_1\ A_2\ \cdots A_{N-1}$
出力
答を整数で出力してください。この問題の制約下で答は必ず整数となります。
最後に改行してください。
サンプル
サンプル1
入力
3 16 8 27 23 20
出力
16
以下が最適な行動の一例です。
-
$t = 0$ のとき
- 表示ボタン $1$ を押す
- 表示ボタン $2$ の有効化時刻が $23$ になる
-
$t = 5$ のとき
- 時短アイテムを $10$ 個連続で消費する
- 表示ボタン $2$ の有効化時刻が $23$ から $13$ に早まる
-
$t = 13$ のとき
- 表示ボタン $2$ が有効になる
- 表示ボタン $2$ を押す
- 表示ボタン $3$ の有効化時刻が $33$ になる
- 即座に時短アイテムを $3$ 個連続で消費する
- 表示ボタン $3$ の有効化時刻が $33$ から $30$ に早まる
-
$t = 16$ のとき
- 時短アイテムを $14$ 個連続で消費する
- 表示ボタン $3$ の有効化時刻が $30$ から $16$ に早まり、表示ボタン $3$ が有効になる
- 表示ボタン $3$ を押す
サンプル2
入力
2 16 8 3 23
出力
24
以下が最適な行動の一例です。
-
$t = 0$ のとき
- 表示ボタン $1$ を押す
- 表示ボタン $2$ の有効化時刻が $23$ になる
-
$t = 23$ のとき
- 表示ボタン $2$ が有効になる
- 睡眠中のため表示ボタン $2$ を押せない
-
$t = 24$ のとき
- 睡眠時間が終わる
- 表示ボタン $2$ を押す
サンプル3
入力
2 100 100 1000000000 10000
出力
0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。