結果

問題 No.155 生放送とBGM
コンテスト
ユーザー yaoshimax
提出日時 2015-02-21 15:01:12
言語 Python2
(2.7.18)
結果
TLE  
実行時間 -
コード長 901 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 25,756 KB
最終ジャッジ日時 2024-06-23 21:35:27
合計ジャッジ時間 14,599 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import math
import copy
def conv(s):
 return int(s[:2])*60+int(s[3:])

N,L=map(int,raw_input().split())
S=map(conv, raw_input().split())
dp= [[0 for k in range(L*60+1+3600)] for i in range(N+1)] 
dp[0][0]=1

alllen=0
for i in range(N):
    s=S[i]
    alllen+=s
    for j in range(N,-1,-1):
        for k in range(L*60+3600,-1,-1):
            if dp[j][k]!=0:
                dp[j+1][min(L*60+3600,k+s)]+=dp[j][k]
        
if alllen <= L*60:
    print N
    exit()

tot=0

for s in S:
    dp2=copy.deepcopy(dp)
    for j in range(0,N+1):
        num = 0
        for k in range(L*60+3600+1):
            if k-s>=0 and j-1 >= 0:
                dp2[j][k] -= dp2[j-1][k-s]
            if k+s >= 60*L and k < 60*L:
                num+=dp2[j][k]
        #print s,"+",j,"elements: ",num
        if num>0:
            tot += (j+1)*num*math.factorial(j)*math.factorial(N-j-1)

print tot*1.0/math.factorial(N)
0