题解：AT_agc072_a [AGC072A] Rhythm Game

首先把问题转化成：$[T_i-X_i,T_i+X_i+D]$ 时间内可以以 $2X_i$ 的时间做任务，要求判断能否做完全部任务。

若只有任务的上界是简单的，按照 $T_i+X_i$ 从小到大做就是对的，证明考虑若不是按这个顺序做的话，交换顺序后仍然合法。

考虑有下界。还是按照 $T_i+X_i$ 排序，若我们跳过了一些小的去做一个大任务的 $i$，对于没做的小的任务 $j$，有 $T_j-X_j<T_j+X_j\leq T_i+X_i= T_i-X_i+2X_i\leq \text{start}+2X_i$。意味着此时所有小的任务的下界都没了，那么按照上述贪心做就是对的，证明类似。

然后就是简单的了。发现对于任意时刻做完了的任务构成一个前缀加上后面的一个单点，设 $f_{i,j}$ 表示做完的任务是 $1,2\cdots,i,j$ 的最小时间，转移是 $O(1)$ 的。

时间复杂度 $O(n^2)$。