結果
問題 | No.155 生放送とBGM |
ユーザー |
![]() |
提出日時 | 2021-05-09 06:40:11 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,579 bytes |
コンパイル時間 | 188 ms |
コンパイル使用メモリ | 81,996 KB |
実行使用メモリ | 633,208 KB |
最終ジャッジ日時 | 2024-09-17 13:30:29 |
合計ジャッジ時間 | 15,045 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 MLE * 5 |
ソースコード
import syssys.setrecursionlimit(10**7)def I(): return int(sys.stdin.readline().rstrip())def MI(): return map(int,sys.stdin.readline().rstrip().split())def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))def LI2(): return list(map(int,sys.stdin.readline().rstrip()))def S(): return sys.stdin.readline().rstrip()def LS(): return list(sys.stdin.readline().rstrip().split())def LS2(): return list(sys.stdin.readline().rstrip())N,L = MI()L *= 60S = LS()songs = [0] # 1-indexfor s in S:m,s = map(int,s.split(':'))songs.append(60*m+s)if sum(songs) <= L:print(N)exit()dp = [[[0]*L for _ in range(N+1)] for _ in range(N+1)]# dp[i][j][k] = 1~i曲目からj曲選んで、合計再生時間k分となる組み合わせdp[0][0][0] = 1for i in range(1,N+1):s = songs[i]for j in range(i+1):for k in range(L):if j >= 1 and k >= s:dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-s]else:dp[i][j][k] = dp[i-1][j][k]fac = [1]for i in range(1,N+1):fac.append(fac[-1]*i)ans = 0for i in range(1,N+1):dp2 = [[0]*L for _ in range(N+1)]# dp2[j][k] = i曲目以外のj曲選んで、合計再生時間k分となる組み合わせs = songs[i]for j in range(N+1):coefficient = fac[j]*fac[N-j-1]/fac[N]for k in range(L):if j >= 1 and k >= s:dp2[j][k] = dp[-1][j][k]-dp2[j-1][k-s]else:dp2[j][k] = dp[-1][j][k]ans += dp2[j][k]*coefficientprint(ans)