SRM 642

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分かかってるんか…