結果
問題 |
No.155 生放送とBGM
|
ユーザー |
![]() |
提出日時 | 2025-04-16 00:10:22 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,471 bytes |
コンパイル時間 | 274 ms |
コンパイル使用メモリ | 81,640 KB |
実行使用メモリ | 283,824 KB |
最終ジャッジ日時 | 2025-04-16 00:11:41 |
合計ジャッジ時間 | 14,763 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 -- * 14 |
ソースコード
import math from collections import defaultdict def main(): n, L = map(int, input().split()) S_str = input().split() S = [] for s in S_str: mm, ss = map(int, s.split(':')) S.append(mm * 60 + ss) T = L * 60 S_total = sum(S) m_max = T // S_total if m_max >= 1: print(n) return ans = 0.0 for i in range(n): other_songs = [S[j] for j in range(n) if j != i] max_sum = T - 1 max_t = len(other_songs) dp = [defaultdict(int) for _ in range(max_t + 1)] dp[0][0] = 1 for d in other_songs: for t in range(len(other_songs), 0, -1): current_sums = list(dp[t-1].items()) for s, cnt in current_sums: new_s = s + d if new_s <= max_sum: dp[t][new_s] += cnt sum_prob = 0.0 for k in range(1, n + 1): t = k - 1 if t < 0 or t > len(other_songs): continue valid = sum(dp[t].values()) total = math.comb(len(other_songs), t) if len(other_songs) >= t else 0 if total == 0: prob_k = 0.0 else: prob_k = valid / total sum_prob += prob_k prob_i = sum_prob / n ans += prob_i print("{0:.10f}".format(ans)) if __name__ == "__main__": main()