問題一覧 > 通常問題

No.3067 +10 Seconds Clock

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

問題文

あなたはとあるゲームのコースをプレイすることになりました.このコースには地点 1,2,,N1, 2, \dots, NNN 個の地点があり,地点 11 がスタート,地点 NN がゴールです.

各整数 1iN11 \leq i \leq N - 1 に対し,あなたは地点 ii から地点 i+1i + 1 へ移動することができます.これには tit_i 秒かかります.それ以外の方法での移動はできません.

このコースには制限時間があります.残りの制限時間はカウントという値によって表され,スタートした時点での値は TT です.以降,11 秒経過するごとに 11 ずつ減少していき,値が 00 になるとゲームオーバーとなります.

また,KK 個の地点 x1,x2,,xKx_1, x_2, \dots, x_K には+10秒時計が設置されています.+10秒時計は,それが置かれた地点にいて,かつカウントの値が 11 以上である場合に獲得できます.獲得した瞬間にカウントの値が 1010 増えます.カウントの値が 00 になった瞬間に+10秒時計のある地点に到達した場合,+10秒時計は獲得できません.

あなたは,ゴールにたどり着くまでに獲得する+10秒時計の数をなるべく少なくしたいです.

ゲームオーバーになることなくゴールにたどり着くまでに獲得する+10秒時計の数の最小値を求めてください.ゲームオーバーになることなくゴールにたどり着けない場合はその旨を報告してください.

なお,+10秒時計を獲得するのにかかる時間は無視するものとします.また,ゴールにたどり着いたと同時にカウントが 00 となった場合もゲームオーバーとなり,ゴールにたどり着けなかったとみなします.

制約

  • 入力は全て整数
  • 3N2×1053 \leq N \leq 2 \times 10^5
  • 1T4×1061 \leq T \leq 4 \times 10^6
  • 1ti201 \leq t_i \leq 20
  • 1KN21 \leq K \leq N - 2
  • 2x1<x2<<xKN12 \leq x_1 < x_2 < \dots < x_K \leq N - 1

入力

入力は以下の形式で標準入力から与えられる.

NN TT
t1t_1 t2t_2 \cdots tN1t_{N-1}
KK
x1x_1 x2x_2 \cdots xKx_K

出力

ゴールにたどり着けない場合,-1 を出力せよ.ゴールにたどり着ける場合,獲得する+10秒時計の個数の最小値を出力せよ.

サンプル

サンプル1
入力
6 20
4 5 6 7 8
3
2 3 5
出力
2

次のように行動することで,22 個の+10秒時計を獲得してゴールにたどり着くことができます.

  • 地点 11 から地点 22 へ移動する.カウントは 204=1620 - 4 = 16 になる.
  • 地点 22 で+10秒時計を獲得し,地点 22 から地点 33 へ移動する.カウントは 16+105=2116 + 10 - 5 = 21 となる.
  • 地点 33 で+10秒時計を獲得せずに,地点 33 から地点 44 へ移動する.カウントは 216=1521 - 6 = 15 となる.
  • 地点 44 から地点 55 へ移動する.カウントは 157=815 - 7 = 8 となる.
  • 地点 55 で+10秒時計を獲得し,地点 55 から地点 66 へ移動する.カウントは 8+108=108 + 10 - 8 = 10 となる.

11 個以下の+10秒時計を獲得してゴールにたどり着くことはできません.上の例で最後の+10秒時計を獲得しなかった場合は地点 66 に到達した時点でカウントが 00 になりますが,これはゴールにたどり着けたとはみなされないことに注意してください.

サンプル2
入力
3 10
10 1
1
2
出力
-1

ゴールにたどり着けません.+10秒時計のある地点に到達した時点でカウントの値が 00 である場合,+10秒時計を獲得できないことに注意してください.

サンプル3
入力
5 4000000
20 20 20 20
3
2 3 4
出力
0

11 つも+10秒時計を獲得せずに,ゴールにたどり着けます.

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