問題一覧 > 通常問題

No.2659 Manga App

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 7
作問者 : 👑 hamamu / テスター : nok0 てんぷら
お気に入りにしたユーザー ProblemId : 10510 / 自分の提出
問題文最終更新日: 2024-03-01 01:15:32
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 419 (順位表) の他の問題:

Problem Statement

hamamu is trying to read through episodes $1$ to $N$ on a manga app.
Pressing an enabled display button $i$ makes episode $i$ readable, but at time $0$ only display button $1$ is enabled and the others are disabled.
A disabled display button cannot be pressed.
When display button $i (1 \le i \le N - 1)$ is pressed at time $t$, the "activation time" of display button $i + 1$ is set to $t + A_i$.
When the activation time of display button $i + 1$ arrives, display button $i + 1$ becomes enabled.

hamamu lives a life of being awake for $B$ hours and then sleeping for $C$ hours, and cannot press display buttons while asleep. Precisely, it is as follows.

  • Let $D = B + C, k = 0, 1, \cdots$.
  • hamamu is awake when the time $t$ satisfies $kD \le t \le kD + B$.
  • hamamu is asleep and cannot press display buttons when the time $t$ satisfies $kD + B \lt t \lt (k + 1)D$.

The manga app has "time-saving items", and hamamu has $X$ of them.
The effect of consuming one time-saving item is as follows. 

    最後に押したのが表示ボタン $i$ で、
    表示ボタン $i + 1$ がまだ有効になっていないとき、
    表示ボタン $i + 1$ の有効化時刻が $1$ 減る（早まる）
Time-saving items can be consumed at any time while awake, and any number of them can be consumed in a row. The time taken to consume a time-saving item and the time taken to press a display button are extremely short and can be ignored.

hamamu pressed display button $1$ at time $0$.
Find the time at which episode $N$ becomes readable when hamamu acts so as to minimize the time taken until pressing display button $N$ and making episode $N$ readable.

Constraints

  • All inputs are integers.
  • $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$

Input

The input is given from standard input in the following format. 
$N\ B\ C\ X$
$A_1\ A_2\ \cdots A_{N-1}$

Output

Print the answer as an integer. Under the constraints of this problem, the answer is always an integer.
Print a newline at the end.

Sample

Sample 1
Input
3 16 8 27
23 20
Output
16

The following is one example of optimal actions.

  • At $t = 0$
    • Press display button $1$.
    • The activation time of display button $2$ becomes $23$.
  • At $t = 5$
    • Consume $10$ time-saving items in a row.
    • The activation time of display button $2$ is moved up from $23$ to $13$.
  • At $t = 13$
    • Display button $2$ becomes enabled.
    • Press display button $2$.
    • The activation time of display button $3$ becomes $33$.
    • Immediately consume $3$ time-saving items in a row.
    • The activation time of display button $3$ is moved up from $33$ to $30$.
  • At $t = 16$
    • Consume $14$ time-saving items in a row.
    • The activation time of display button $3$ is moved up from $30$ to $16$, and display button $3$ becomes enabled.
    • Press display button $3$.
It is impossible to enable display button $3$ at $t \lt 16$, so the answer is $16$.

Sample 2
Input
2 16 8 3
23
Output
24

The following is one example of optimal actions.

  • At $t = 0$
    • Press display button $1$.
    • The activation time of display button $2$ becomes $23$.
  • At $t = 23$
    • Display button $2$ becomes enabled.
    • Display button $2$ cannot be pressed because hamamu is asleep.
  • At $t = 24$
    • The sleeping period ends.
    • Press display button $2$.
$3$ time-saving items are left over, but it is impossible to enable display button $3$ at $t < 24$, so this is (one example of) optimal actions.

Sample 3
Input
2 100 100 1000000000
10000
Output
0

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