Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 265 B問題 Explore

AtCoder ABC ABC265 B問題 200 pts

問題

提出解答

問題の概要

$N$ 個の部屋からなる洞窟がある. $N$ 個の部屋は1列につながっており, 入り口から順に部屋 $1,2, \dots, N$ と名付けられている.

最初, 部屋 $1$ におり, 持ち時間が $T$ である. $i=1,2, \dots, N-1$ に対して, 持ち時間 $A_i$ だけ消費して部屋 $i$ から部屋 $(i+1)$ に移動することとができる. ただし, 持ち時間が $0$ 以下になるような移動はできない. また, これら以外に部屋を移動することはできない.

ここで, $j=1,2, \dots, M$ について, 部屋 $X_j$ にはボーナスが用意されており, この部屋に到達したら持ち時間が $Y_j$ 増加する.

この条件下で部屋 $N$ に移動できるか?

制約

$1 \leq N \leq 10^5$
$0 \leq M \leq N-2$
$1 \leq T \leq 10^9$
$1 \leq A_i \leq 10^9$
$1 \lt X_1 \lt \dots \lt X_M \lt N$
$1 \leq Y_i \leq 10^9$

解法

実際にシミュレーションすればよい. なお, 以下のことに注意すること.

ボーナスが無い部屋についても「持ち時間が $0$ 増加するボーナス」と考えると, 全ての部屋にボーナスを付けることができる.
持ち時間の管理は必ず $A_i$ だけ減らした後にボーナスを発生させること.
持ち時間がちょうど $0$ になる移動ができないこと.