GigaCode2019 E - 車の乗り継ぎ (100)
$ dp[i番の車に乗って][j番目の地点にいる時] の最短時間を求める
最終的に$ dp[i][i] の形しか使わなかったのでj側は不要そう
各i毎にそれ以前のjに対して、$ X_i - X_j \le d_jな物のみ扱う
$ dp[j][j] + (X_i - X_j) / v_j が最小なものを$ dp[j][j] の値とする
最終的にLに到達可能なiの中で$ dp[i][i] + (L - X_i) / v_i が最小の物が答え
各i毎にそれ以前の全ての要素を見るので$ O(N^2)