coins - atcoder contest

I - Coins

educational dynamming programming contest
coins

There’s n coins, and 2^n possible flip sequences. There’s a closed form expression for this when the probability of the coins being heads is the same for all coins. That is not the case here.

The probability of a sequence of independent flips is the product of each flip’s proability (p_i if heads and (1 - p_i) if tails).

You could sum up all of those products in which there’s more heads than tails (# heads >= n/2 + 1). However, n < 3000, and there’s (n choose (n/2 + 1)) of these products.

Notice that these products can share segments:
P(H1 T2 H3 T4 H5) = P(H1 T2 H3 T4) * P(H5)
P(H1 T2 H3 T4 T5) = P(H1 T2 H3 T4) * P(T5)

A very intuitive dynammic programming solution follows:
dp[i][j] = P(getting i heads in first j flips) = P(Hj) * P(getting i - 1 heads in the first j - 1 flips) + P(Tj) * P(getting i heads in the first j - 1 flips)
my submission

#include<iostream>
#include<iomanip>

using namespace std;

int n;

long double P[3000];
long double dp[3000][3000];

int main() {
	cin >> n;
	
	for (int i = 1;i < n + 1;++i) cin >> P[i];
	
	dp[0][0] = 1;
	
	for (int flips = 1;flips < n + 1;++flips)
		dp[0][flips] = (1.0 - P[flips]) * dp[0][flips - 1];
	
	for (int flips = 1;flips < n + 1;++flips) {
		for (int heads = 1;heads <= flips;++heads) {
			dp[heads][flips] = P[flips] * dp[heads - 1][flips - 1] + (1 - P[flips]) * dp[heads][flips - 1];
		}
	}
	
	long double more_heads = 0;
	
	for (int heads = n/2 + 1;heads < n + 1;++heads) more_heads += dp[heads][n];
	
	cout << std::setprecision(9) << more_heads << endl;
}