結果

問題 No.155 生放送とBGM
コンテスト
ユーザー yaoshimax
提出日時 2015-02-21 15:42:22
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 198 ms / 6,000 ms
コード長 1,748 bytes
コンパイル時間 918 ms
コンパイル使用メモリ 89,836 KB
実行使用メモリ 20,992 KB
最終ジャッジ日時 2024-06-23 21:36:41
合計ジャッジ時間 2,677 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:29:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   29 |       scanf("%d:%d",&a,&b);
      |       ~~~~~^~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#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