No.3067 +10 Seconds Clock
タグ : / 解いたユーザー数 109
作問者 : 👑


問題文
あなたはとあるゲームのコースをプレイすることになりました.このコースには地点 $1, 2, \dots, N$ の $N$ 個の地点があり,地点 $1$ がスタート,地点 $N$ がゴールです.
各整数 $1 \leq i \leq N - 1$ に対し,あなたは地点 $i$ から地点 $i + 1$ へ移動することができます.これには $t_i$ 秒かかります.それ以外の方法での移動はできません.
このコースには制限時間があります.残りの制限時間はカウントという値によって表され,スタートした時点での値は $T$ です.以降,$1$ 秒経過するごとに $1$ ずつ減少していき,値が $0$ になるとゲームオーバーとなります.
また,$K$ 個の地点 $x_1, x_2, \dots, x_K$ には+10秒時計が設置されています.+10秒時計は,それが置かれた地点にいて,かつカウントの値が $1$ 以上である場合に獲得できます.獲得した瞬間にカウントの値が $10$ 増えます.カウントの値が $0$ になった瞬間に+10秒時計のある地点に到達した場合,+10秒時計は獲得できません.
あなたは,ゴールにたどり着くまでに獲得する+10秒時計の数をなるべく少なくしたいです.
ゲームオーバーになることなくゴールにたどり着くまでに獲得する+10秒時計の数の最小値を求めてください.ゲームオーバーになることなくゴールにたどり着けない場合はその旨を報告してください.
なお,+10秒時計を獲得するのにかかる時間は無視するものとします.また,ゴールにたどり着いたと同時にカウントが $0$ となった場合もゲームオーバーとなり,ゴールにたどり着けなかったとみなします.
制約
- 入力は全て整数
- $3 \leq N \leq 2 \times 10^5$
- $1 \leq T \leq 4 \times 10^6$
- $1 \leq t_i \leq 20$
- $1 \leq K \leq N - 2$
- $2 \leq x_1 < x_2 < \dots < x_K \leq N - 1$
入力
入力は以下の形式で標準入力から与えられる.
$N$ $T$ $t_1$ $t_2$ $\cdots$ $t_{N-1}$ $K$ $x_1$ $x_2$ $\cdots$ $x_K$
出力
ゴールにたどり着けない場合,-1
を出力せよ.ゴールにたどり着ける場合,獲得する+10秒時計の個数の最小値を出力せよ.
サンプル
サンプル1
入力
6 20 4 5 6 7 8 3 2 3 5
出力
2
次のように行動することで,$2$ 個の+10秒時計を獲得してゴールにたどり着くことができます.
- 地点 $1$ から地点 $2$ へ移動する.カウントは $20 - 4 = 16$ になる.
- 地点 $2$ で+10秒時計を獲得し,地点 $2$ から地点 $3$ へ移動する.カウントは $16 + 10 - 5 = 21$ となる.
- 地点 $3$ で+10秒時計を獲得せずに,地点 $3$ から地点 $4$ へ移動する.カウントは $21 - 6 = 15$ となる.
- 地点 $4$ から地点 $5$ へ移動する.カウントは $15 - 7 = 8$ となる.
- 地点 $5$ で+10秒時計を獲得し,地点 $5$ から地点 $6$ へ移動する.カウントは $8 + 10 - 8 = 10$ となる.
$1$ 個以下の+10秒時計を獲得してゴールにたどり着くことはできません.上の例で最後の+10秒時計を獲得しなかった場合は地点 $6$ に到達した時点でカウントが $0$ になりますが,これはゴールにたどり着けたとはみなされないことに注意してください.
サンプル2
入力
3 10 10 1 1 2
出力
-1
ゴールにたどり着けません.+10秒時計のある地点に到達した時点でカウントの値が $0$ である場合,+10秒時計を獲得できないことに注意してください.
サンプル3
入力
5 4000000 20 20 20 20 3 2 3 4
出力
0
$1$ つも+10秒時計を獲得せずに,ゴールにたどり着けます.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。