15411019's blog

By 15411019, history, 5 years ago, In English

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;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it