I am trying to solve this problem from Educational DP contest(atcoder) and having some issues with my code. Its working for all small test cases I can think of but when I submit I am getting runtime error. If anyone can tell what I am doing wrong, I am beginner.
Code:
#include <bits/stdc++.h>
using namespace std;
int n;
double prob[3001];
double dp[3001][3001];
bool vis[3001][3001];
double f(int c, int h){
if(c==0 and h==0) return 1.0;
if(c<0) return 0.0;
if(vis[c][h]) return dp[c][h];
dp[c][h] = (double)prob[c]*f(c-1,h-1)+(double)(1-prob[c])*f(c-1,h);
vis[c][h] = true;
return dp[c][h];
}
int main(){
memset(dp,-1,sizeof(dp));
cin>>n;
for(int i=1;i<=n;i++){
cin>>prob[i];
}
double ans = 0.0;
for(int i=n/2+1;i<=n;i++){
ans = ans + f(n,i);
}
cout<< fixed <<setprecision(20)<<ans;
}