No.54

$v$ 個お菓子を持った状態で $i$ 番目の家の後に $j$ 番目の家を訪れてお菓子をもらった方がより多くのお菓子をもらえる条件は,

$$v \lt T_i,\ v \lt T_j \\ v + V_i \lt T_j \\ v + V_j \geq T_i$$

となる. これを変形して,

$$T_i - V_j \leq v \lt T_j - V_i \\ T_i + V_i \lt T_j + V_j$$

となる. よって, $T_i + V_i$ が小さい順に訪問する方がより多くのお菓子をもらえるので, $T_i + V_i$ でソートしておいてこの順で訪問するかしないかを考えればいい.

$i$ 番目の家まで訪れたときに $v$ 個お菓子をもらえるかどうかを $B(i, v)$ すると,

$$B(i, v) = B(i - 1, v) \lor B(i - 1, v - V_i)$$

となる. これを DP で計算し, $B(N, v) = {\rm true}$ となる最大の $v$ が答えとなる. もらえるお菓子の最大数は $\max(T_i + V_i) - 1$ であるので, $O(N(V + T))$ で計算できる.