問題は平均速度 $x_i$ で時間が $y_i$ であるようなコースをいくつか選び、平均速度を最小化するものと言い換えられます。平均速度を $S$ 以下とできるかを判定しましょう。
コース $i,j,k, \cdots$ を使うとして $x_iy_i + x_jy_j + x_ky_k + \cdots \leq S \left( y_i + y_j + y_k + \cdots \right)$ を満たしたいです。これを変形すると $(x_i-S)y_i + (x_j-S)y_j + (x_k-S)y_k + \cdots \leq 0$ と同値であることが分かります。
よって、 $dp[a]$ を地点 $a$ にたどり着く方法でそれまでの $(x_i-S)y_i$ の合計が最小となるものとしてこれを $a$ の昇順に埋めていくことで判定問題を $O(n+c)$ で解くことができます。

平均速度が明らかに \(\max \left( s \right)\) を上回ることがないので、二分探索と組み合わせて全体で \(O( \left( n+c \right) \log \max \left( s \right) )\) で解くことができます。 実装の際、 \(S,dp\) を小数で管理して二分探索の区間の長さが一定以下になれば打ち切るとしても問題なく正解できます。