ICPC 2022 A Solution

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<double> p;
vector<double> dp;

double sim(int m)
{
    if(dp[m]!=-1) return dp[m];

    int numLeft = 0;
    for(int i=0;i<n;i++)
    {
        if((m>>i) & 1) continue;
        numLeft++;
    }
    if(numLeft<=2) return dp[m] = 0;

    double pAllUp = 1;
    double pAllDown = 1;
    for(int i=0;i<n;i++)
    {
        if((m>>i) & 1) continue;
        pAllUp *= p[i];
        pAllDown *= (1-p[i]);
    }

    double pElimination = 0;
    for(int i=0;i<n;i++)
    {
        if( (m>>i) & 1 ) continue;
        pElimination += pAllUp/p[i] * (1-p[i]);
        pElimination += pAllDown/(1-p[i]) * p[i];
    }

    double ev = 1/pElimination;
    for(int i=0;i<n;i++)
    {
        if( (m>>i) & 1 ) continue;
        double piEliminated = pAllUp/p[i] * (1-p[i]) + pAllDown/(1-p[i]) * p[i];
        ev += piEliminated / pElimination * sim( m | (1<<i) );
    }

    return dp[m] = ev;

}

int main()
{
    cin >> n;
    p.resize(n);
    for(int i=0;i<n;i++) cin >> p[i];
    dp.resize(1<<n, -1);

    printf("%.10f\n", sim(0));
}