結果
問題 | No.155 生放送とBGM |
ユーザー |
![]() |
提出日時 | 2021-05-09 06:35:33 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,609 bytes |
コンパイル時間 | 228 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 638,720 KB |
最終ジャッジ日時 | 2024-09-17 13:25:35 |
合計ジャッジ時間 | 26,547 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 MLE * 2 -- * 12 |
ソースコード
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+1) 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+1):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+1) for _ in range(N+1)]# dp2[j][k] = i曲目以外のj曲選んで、合計再生時間k分となる組み合わせs = songs[i]for j in range(N+1):for k in range(L+1):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]for j in range(N+1):for k in range(L):ans += dp2[j][k]*fac[j]*fac[N-j-1]/fac[N]print(ans)