Language: C++

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <list>
#include <climits>
#include <numeric>

#define TEST_MODE 0

using namespace std;


template <typename T>
void printVector(vector<T> v)
{
    for(auto & val : v)
        cout << val << "\t";
    cout << "\n";
}

void getProbabilityRecur(const vector<double> &p, vector<double> & res, vector<bool> &tmp, int count, int index, int N)
{
    if(index > N) return;

    if(index - 1 - count >= (N/2) + 1)
        return;

    if(index == N)
    {
        if(count >= (N/2) + 1 )
        {
            double value = 1;

            for(int i = 0; i < N; ++i)
                value *= (tmp[i] ? p[i] : (1 - p[i]));

            //cout << value << ".\n";
            res.push_back(value);
        }
        return;
    }

    tmp[index] = true;
    getProbabilityRecur(p, res, tmp, count + 1, index + 1, N);
    tmp[index] = false;
    getProbabilityRecur(p, res, tmp, count, index + 1, N);
}

double getProbabilitySum(const vector<double> & p, int N)
{
    vector<double> res;
    vector<bool> tmp(N, false);
    getProbabilityRecur(p, res, tmp, 0, 0, N);

    return accumulate(res.begin(), res.end(), 0.0);
}

double getDPProbabilitySum(const vector<double> & p, int N)
{
    vector<double> dp(N + 1);
    dp[0] = 1;

    //dp[0...i] : This will be probability of j heads where 0 <= j <= i,
    //              i.e dp[0] will have 0 heads,
    //              i.e dp[1] will have 1 heads,
    //              i.e dp[j] will have j heads,
    //              i.e dp[i] will have i heads,
    //              when coin is tossed i times.

    for(int coin = 0; coin < N; ++coin)
    {
        // We go backward as we want the previous results intact while computing larger head count
        // We are counting probability of i heads with coin number of coins
        for(int i = coin + 1; i >= 0; --i)
        {
            if(i - 1 >= 0)
                dp[i] = dp[i - 1] * p[coin] + dp[i] * (1 - p[coin]);
            else
                dp[i] = dp[i] * (1 - p[coin]);
        }
    }

    double sum = 0;
    for(int i = (N + 1)/2 ; i <= N; ++i)
        sum += dp[i];

    return sum;
}

class Test
{
    private:
    vector<double> test1;
    vector<double> test2;
    vector<double> test3;

    public:
    Test(): test1({0.30, 0.60, 0.80}),
            test2({0.5}),
            test3({0.42, 0.01, 0.42, 0.99, 0.42}){}

    void runTestsRecur()
    {
        double value = getProbabilitySum(test1, test1.size());
        assert(std::abs(value - 0.612) < 0.001);

        value = getProbabilitySum(test2, test2.size());
        assert(std::abs(value - 0.5) < 0.001);

        value = getProbabilitySum(test3, test3.size());
        assert(std::abs(value - 0.382182) < 0.001);

        cout << "RECURRSION TESTS PASSED\n";
    }

    void runTestsDP()
    {
        double value = getDPProbabilitySum(test1, test1.size());
        assert(std::abs(value - 0.612) < 0.001);

        value = getDPProbabilitySum(test2, test2.size());
        assert(std::abs(value - 0.5) < 0.001);

        value = getDPProbabilitySum(test3, test3.size());
        assert(std::abs(value - 0.382182) < 0.001);

        cout << "DP TESTS PASSED\n";
    }
};

int main()
{
#ifdef TEST_MODE

    Test test;
    test.runTestsRecur();
    test.runTestsDP();

#else
    int N;
    cin >> N;
    vector<double> p(N);

    for(int i = 0; i < N; ++i)
        scanf("%lf", &p[i]);

    //cout << getProbabilitySum(p, N) << "\n";
    cout << getDPProbabilitySum(p, N) << "\n";
#endif

    return 0;
}


Compiler output:
a.cc: In member function 'void Test::runTestsRecur()':
a.cc:113:9: error: 'assert' was not declared in this scope
  113 |         assert(std::abs(value - 0.612) < 0.001);
      |         ^~~~~~
a.cc:15:1: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'
   14 | #include <numeric>
  +++ |+#include <cassert>
   15 | 
a.cc: In member function 'void Test::runTestsDP()':
a.cc:127:9: error: 'assert' was not declared in this scope
  127 |         assert(std::abs(value - 0.612) < 0.001);
      |         ^~~~~~
a.cc:127:9: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'