fork download
copy 
  1. #include <iostream>
  2. #include <sstream>
  3. #include <string>
  4. #include <vector>
  5. #include <deque>
  6. #include <queue>
  7. #include <set>
  8. #include <map>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <utility>
  12. #include <cmath>
  13. #include <cstdlib>
  14. #include <ctime>
  15. #include <cstdio>
  16.  
  17. using namespace std;
  18.  
  19. #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
  20. #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
  21.  
  22.  
  23. #define eps 1.0E-12
  24.  
  25. int M,N;
  26. double p[310][3010];
  27. int len[310];
  28. double q[310][3010];
  29. double score[310][3010],dp[310][3010];
  30.  
  31. void update(int t, double prob){
  32.     int i;
  33.     double ignore_sum = 0.0;
  34.  
  35.     for(i=len[t];i>=0;i--){
  36.         q[t][i+1] += q[t][i] * prob;
  37.         q[t][i] *= (1.0 - prob);
  38.         if(q[t][i] < 1.0E-50) q[t][i] = 0.0;
  39.     }
  40.  
  41.     if(ignore_sum + q[t][len[t]+1] < eps){
  42.         ignore_sum += q[t][len[t]+1];
  43.     } else {
  44.         len[t]++;
  45.     }
  46. }
  47.  
  48. int main(void){
  49.     int tmp,i,j,k;
  50.     freopen("MIDAU.INP","r",stdin);
  51.     freopen("MIDAU.OUT","w",stdout);
  52.  
  53.     scanf("%d%d",&N,&M);
  54.     REP(i,N) REP(j,M){
  55.         scanf("%d",&tmp);
  56.         p[j][i] = tmp / 1000.0;
  57.     }
  58.  
  59.     REP(i,M){
  60.         q[i][0] = 1.0;
  61.         REP(j,N) update(i,p[i][j]);
  62.     }
  63.  
  64.     REP(i,M){
  65.         double expected = 0.0;
  66.         REP(j,len[i]+1) expected += q[i][j] * j;
  67.         score[i][len[i]] = expected;
  68.  
  69.         double sumq = 0.0;
  70.         for(j=len[i]-1;j>=0;j--){
  71.             sumq += q[i][j+1];
  72.             score[i][j] = score[i][j+1] - sumq;
  73.         }
  74.     }
  75.  
  76.     REP(i,M) REP(j,N+1) REP(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]);
  77.  
  78.     double ans = 0.0;
  79.     REP(i,N+1) ans = max(ans, dp[M][i]);
  80.     printf("%.12f\n",ans);
  81.  
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0s 5520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HyxG4e
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!