結果
問題 |
No.155 生放送とBGM
|
ユーザー |
![]() |
提出日時 | 2015-03-26 09:26:13 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 133 ms / 6,000 ms |
コード長 | 1,222 bytes |
コンパイル時間 | 1,264 ms |
コンパイル使用メモリ | 159,964 KB |
実行使用メモリ | 18,816 KB |
最終ジャッジ日時 | 2024-06-29 00:59:52 |
合計ジャッジ時間 | 2,894 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
ソースコード
#include "bits/stdc++.h" using namespace std; int getnum(char c){ return c - '0'; } double dp[51][36002]; double predp[51][36002]; double functional[51]; int S[51]; int main() { int N, L; cin >> N >> L; L *= 60; double ans = 0; int sum = 0; for (int i = 0; i < N; i++) { string temp; cin >> temp; int time = getnum(temp[0]) * 600 + getnum(temp[1]) * 60 + getnum(temp[3]) * 10 + getnum(temp[4]); if (time > L) time = L; S[i] = time; sum += time; } if (L >= sum){ cout << N << endl; return 0; } dp[0][0] = 1; for (int i = 0; i < N; i++) { for (int j = i; j >= 0; j--) { for (int k = 0; S[i] + k <= L * 2; k++) { if (!dp[j][k]) continue; dp[j + 1][S[i] + k] += dp[j][k]; } } } functional[0] = 1; for (int i = 1; i < 51; i++) { functional[i] = functional[i - 1] * i; } double sump = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { for (int k = 0; k < L; k++) { predp[j][k] = dp[j][k]; if (j - 1 >= 0 && k - S[i] >= 0){ predp[j][k] -= predp[j - 1][k - S[i]]; } sump += predp[j][k] * functional[N - j - 1] * functional[j]; } } } sump /= functional[N]; ans += sump; printf("%.14f", ans); cin >> ans; }