fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define foru(i,n) for((i)=0;(i)<(int)(n);(i)++)
  4. #define pi 1.0E-12
  5. int M,N;
  6. double p[350][3050];
  7. int len[350];
  8. double q[350][3050];
  9. double score[350][3050],dp[350][3050];
  10. void update(int t, double dtr){
  11.     int i;
  12.     double descent = 0.0;
  13.  
  14.     for(i=len[t];i>=0;i--){
  15.         q[t][i+1] += q[t][i] * dtr;
  16.         q[t][i] *= (1.0 - dtr);
  17.         if(q[t][i] < 1.0E-50) q[t][i] = 0.0;
  18.     }
  19.  
  20.     if(descent + q[t][len[t]+1] < pi){
  21.         descent += q[t][len[t]+1];
  22.     } else {
  23.         len[t]++;
  24.     }
  25. }
  26.  
  27. int main(void){
  28.     int tam,i,j,k;
  29.     freopen("MIDAU.inp","r",stdin);
  30.      freopen("MIDAU.out","w",stdout);
  31.      scanf("%d%d",&N,&M);
  32.     foru(i,N) foru(j,M){
  33.       scanf("%d",&tam);
  34.         p[j][i] = tam / 1000.0;
  35.     }
  36.  
  37.     foru(i,M){
  38.         q[i][0] = 1.0;
  39.         foru(j,N) update(i,p[i][j]);
  40.     }
  41.  
  42.     foru(i,M){
  43.         double rgnjoi = 0.0;
  44.         foru(j,len[i]+1) rgnjoi += q[i][j] * j;
  45.         score[i][len[i]] = rgnjoi;
  46.  
  47.         double tink4 = 0.0;
  48.         for(j=len[i]-1;j>=0;j--){
  49.             tink4 += q[i][j+1];
  50.             score[i][j] = score[i][j+1] - tink4;
  51.         }
  52.     }
  53.  
  54.     foru(i,M) foru(j,N+1) foru(k,len[i]+1) if(j+k <= N) dp[i+1][j+k] = max(dp[i+1][j+k], dp[i][j] + score[i][k]);
  55.  
  56.     double itk4 = 0.0;
  57.     foru(i,N+1) itk4 = max(itk4, dp[M][i]);
  58.  
  59.     printf("%.12f\n",itk4);
  60.  
  61.     return 0;
  62. }
  63.  
Success #stdin #stdout 0s 5624KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/I6EIQp
language:
C++ (gcc 8.3)
created:
4 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!