結果
問題 |
No.155 生放送とBGM
|
ユーザー |
![]() |
提出日時 | 2025-06-12 14:32:55 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,541 bytes |
コンパイル時間 | 362 ms |
コンパイル使用メモリ | 82,312 KB |
実行使用メモリ | 172,836 KB |
最終ジャッジ日時 | 2025-06-12 14:33:11 |
合計ジャッジ時間 | 14,717 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 -- * 14 |
ソースコード
import sys from math import comb def main(): n, L = map(int, sys.stdin.readline().split()) s_list = sys.stdin.readline().split() S = [] for s in s_list: mm, ss = map(int, s.split(':')) S.append(mm * 60 + ss) T = L * 60 S_total = sum(S) if S_total <= T: print(n) return E = 0.0 for i in range(n): song_i = S[i] others = S[:i] + S[i+1:] m_max = len(others) total_prob = 0.0 for k in range(1, n + 1): m = k - 1 if m > m_max: continue a_max = T - 1 # 因为 t <= T-1 if a_max < 0: continue # 初始化动态规划表 dp = [[0] * (a_max + 1) for _ in range(m + 1)] dp[0][0] = 1 for s in others: for current_m in range(m, 0, -1): for current_a in range(a_max, s - 1, -1): if dp[current_m - 1][current_a - s]: dp[current_m][current_a] += dp[current_m - 1][current_a - s] count = sum(dp[m][a] for a in range(a_max + 1)) total = comb(len(others), m) if total == 0: prob = 0.0 else: prob = count / total total_prob += (1.0 / n) * prob E += total_prob print("{0:.10f}".format(E)) if __name__ == '__main__': main()