fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define esp 1.0E-12
  4. double q[3005][3005],p[3005][3005],dp[3005][3005],sc[3005][3005];
  5. int n,m,len[3005];
  6. void update(int t,double prob)
  7. {
  8.     int i;
  9.     double isp=0.0;
  10.     for(i=len[t];i>=0;i--)
  11.     {
  12.         q[t][i+1]+=q[t][i]*prob;
  13.         q[t][i]*=(1.0-prob);
  14.         if (q[t][i]<1.0E-50) q[t][i]=0.0;
  15.     }
  16.     if (isp+q[t][len[t]+1]<esp)
  17.         isp+=q[t][len[t]+1];
  18.     else len[t]++;
  19. }
  20. int main(void)
  21. {
  22.     int tmp,i,j,k;
  23.     ifstream fi ("MIDAU.inp");
  24.     ofstream fo ("MIDAU.out");
  25.     fi>>n>>m;
  26.     for (i=0;i<n;i++)
  27.         for (j=0;j<m;j++)
  28.     {
  29.         fi>>tmp;
  30.         p[j][i]=tmp/1000.0;
  31.     }
  32.     for (i=0;i<m;i++)
  33.     {
  34.         q[i][0]=1.0;
  35.         for (j=0;j<n;j++) update(i,p[i][j]);
  36.     }
  37.     for (i=0;i<m;i++)
  38.     {
  39.         double ex=0.0;
  40.         for(j=0;j<len[i]+1;j++) ex+=q[i][j]*j;
  41.         sc[i][len[i]]=ex;
  42.         double sp=0.0;
  43.         for(j=len[i]-1;j>=0;j--) sp+=q[i][j+1];
  44.         sc[i][j]=sc[i][j+1]-sp;
  45.     }
  46.     for (i=0;i<m;i++)
  47.         for (j=0;j<n+1;j++)
  48.             for (k=0;k<len[i]+1;k++)
  49.             if ((j+k)<=n ) dp[i+1][j+k]=max(dp[i+1][j+k],dp[i][j]+sc[i][k]);
  50.     double ans=0.0;
  51.     for (i=0;i<n+1;i++)
  52.         ans=max(ans,dp[m][i]);
  53.     fo<<ans;
  54. }
  55.  
Success #stdin #stdout 0s 5660KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oKSIRh
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!