fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
  3. #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
  4.  
  5. #define eps 1.0E-12
  6. using namespace std;
  7.  
  8. fstream fi,fo;
  9.  
  10. int M,N;
  11. double p[310][3010];
  12. int len[310];
  13. double q[310][3010];
  14. double score[310][3010],dp[310][3010];
  15.  
  16. void update(int t, double prob){
  17.     int i;
  18.     double ignore_sum = 0.0;
  19.  
  20.     for(i=len[t];i>=0;i--){
  21.         q[t][i+1] += q[t][i] * prob;
  22.         q[t][i] *= (1.0 - prob);
  23.         if(q[t][i] < 1.0E-50) q[t][i] = 0.0;
  24.     }
  25.  
  26.     if(ignore_sum + q[t][len[t]+1] < eps){
  27.         ignore_sum += q[t][len[t]+1];
  28.     } else {
  29.         len[t]++;
  30.     }
  31. }
  32.  
  33. int main(void){
  34.     fi.open("MIDAU.INP",ios::in);
  35.     fo.open("MIDAU.OUT",ios::out);
  36.     int tmp,i,j,k;
  37.  
  38.     fi >> N >> M;
  39.     REP(i,N) REP(j,M){
  40.         fi >> tmp;
  41.         p[j][i] = tmp / 1000.0;
  42.     }
  43.  
  44.     REP(i,M){
  45.         q[i][0] = 1.0;
  46.         REP(j,N) update(i,p[i][j]);
  47.     }
  48.  
  49.     REP(i,M){
  50.         double expected = 0.0;
  51.         REP(j,len[i]+1) expected += q[i][j] * j;
  52.         score[i][len[i]] = expected;
  53.  
  54.         double sumq = 0.0;
  55.         for(j=len[i]-1;j>=0;j--){
  56.             sumq += q[i][j+1];
  57.             score[i][j] = score[i][j+1] - sumq;
  58.         }
  59.     }
  60.  
  61.     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]);
  62.  
  63.     double ans = 0.0;
  64.     REP(i,N+1) ans = max(ans, dp[M][i]);
  65.     fo.precision(12);
  66.     fo << ans;
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0s 5552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zxZFtN
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!