結果

問題 No.155 生放送とBGM
ユーザー yaoshimaxyaoshimax
提出日時 2015-02-21 15:42:22
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 262 ms / 6,000 ms
コード長 1,748 bytes
コンパイル時間 654 ms
コンパイル使用メモリ 88,140 KB
実行使用メモリ 20,664 KB
最終ジャッジ日時 2023-09-06 02:45:31
合計ジャッジ時間 3,295 ms
ジャッジサーバーID
(参考情報)
judge13 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 254 ms
20,656 KB
testcase_01 AC 255 ms
20,664 KB
testcase_02 AC 262 ms
20,656 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 25 ms
6,148 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 237 ms
20,616 KB
testcase_07 AC 3 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 5 ms
5,012 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 6 ms
5,052 KB
testcase_12 AC 6 ms
5,304 KB
testcase_13 AC 3 ms
4,376 KB
testcase_14 AC 201 ms
17,748 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>

using namespace std;
int main(){
   int N,L;
   cin >> N >> L;
   int s[N];
   int sum=0;
   for( int i = 0 ; i < N ; i++){
      int a,b;
      scanf("%d:%d",&a,&b);
      s[i]=a*60+b;
      sum+=s[i];
   }
   L*=60;
   if( sum <= L ){
      printf("%.9f\n",(double)N);
      return 0;
   }
   double fact[N+1];
   fact[0]=1;
   for( int i = 1; i <=N; i++) fact[i]=fact[i-1]*i;
   double dp[N+1][L+3600];
   for( int i = 0 ; i <=N; i++ ) for( int j =0 ; j <L+3600;j++) dp[i][j]=0;
   dp[0][0]=1;
   for( int i = 0 ; i <N ; i++ ){
      for( int k = N ; k >=0 ; k-- ){
         for( int j = L+3599 ; j >=0; j-- ){
            if(dp[k][j] != 0 ){
               //cout << k+1 << ", "<< min(L+3599,j+s[i]) << endl;
               dp[k+1][min(L+3599,j+s[i])]+= dp[k][j];
            }
         }
      }
   }
    
   double dp2[N+1][L+3600];
   double ret =0;
   for( int i = 0 ; i < N ; i++ ){
      for( int k = 0 ; k < N ; k++ ){
         double tot = 0;
         for( int j = 0 ; j < L+3600; j++){
            dp2[k][j]=dp[k][j];
            if( k-1 >= 0 && j-s[i] >= 0 ){
               dp2[k][j]-=dp2[k-1][j-s[i]];
            }
            if( j < L && j+s[i] >= L && dp2[k][j] > 0){
               //cout << s[i]<<", "<<k << ", "<<dp2[k][j]<<endl;
               ret += (k+1)*dp2[k][j]*fact[k]*fact[N-k-1];
            }
         }
      }
   }
   printf("%.9f\n", ret/fact[N]);
   return 0;
}
0