結果
問題 |
No.155 生放送とBGM
|
ユーザー |
![]() |
提出日時 | 2025-06-12 13:15:11 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,675 bytes |
コンパイル時間 | 380 ms |
コンパイル使用メモリ | 82,944 KB |
実行使用メモリ | 275,584 KB |
最終ジャッジ日時 | 2025-06-12 13:17:42 |
合計ジャッジ時間 | 14,883 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 -- * 14 |
ソースコード
import sys def main(): N, L = map(int, sys.stdin.readline().split()) S = [] sum_total = 0 for s in sys.stdin.readline().split(): mm, ss = map(int, s.split(':')) sec = mm * 60 + ss S.append(sec) sum_total += sec T = L * 60 if sum_total <= T: print(N) return # Precompute combinations max_n = N - 1 comb = [[0] * (max_n + 1) for _ in range(max_n + 1)] for n in range(max_n + 1): comb[n][0] = 1 for k in range(1, n + 1): comb[n][k] = comb[n-1][k-1] + comb[n-1][k] expect = 0.0 for k in range(N): s_list = S[:k] + S[k+1:] n = len(s_list) T_target = T max_j = n max_t = T_target - 1 # Initialize DP dp = [[0] * (max_t + 1) for _ in range(max_j + 1)] dp[0][0] = 1 for s in s_list: for j in range(max_j, 0, -1): for t in range(max_t, s - 1, -1): if dp[j-1][t - s]: dp[j][t] += dp[j-1][t - s] # Calculate cnt[j] cnt = [0] * (max_j + 1) for j in range(max_j + 1): cnt[j] = sum(dp[j][t] for t in range(T_target)) # Calculate probability for current song k p = 0.0 for i in range(1, N + 1): j = i - 1 if j < 0 or j > max_j: continue c = comb[max_j][j] if j <= max_j else 0 if c == 0: prob = 0.0 else: prob = cnt[j] / c p += prob / N expect += p print("{0:.10f}".format(expect)) if __name__ == '__main__': main()