Easy
dp[i]:=時刻iにバスがつく確率、でdpを更新して期待値求めればいいです。
struct WaitingForBus { vector<int> time; vector<int> prob; int s; double dp[200110]; double whenWillBusArrive(vector<int> _time, vector<int> _prob, int _s) { time = _time, prob = _prob, s = _s; int n = sz(time); dp[0] = 1; rep(i, 0, s) { rep(j, 0, n) { dp[i + time[j]] += dp[i] * prob[j] / 100.0; } } double res = 0; rep(i, 0, 100000 + 10) { res += dp[s + i] * i; } return res; } };
5 minutes 39 secs。これでも5分かかってるんか…