問題一覧 > 通常問題

No.3067 +10 Seconds Clock

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 109
作問者 : 👑 AngrySadEight / テスター : friedrice hamamu
1 ProblemId : 11767 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-03-20 11:09:43

問題文

あなたはとあるゲームのコースをプレイすることになりました.このコースには地点 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。