結果
問題 | No.155 生放送とBGM |
ユーザー | d01phn |
提出日時 | 2021-02-02 13:00:37 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 439 ms / 6,000 ms |
コード長 | 2,128 bytes |
コンパイル時間 | 1,578 ms |
コンパイル使用メモリ | 170,516 KB |
実行使用メモリ | 369,444 KB |
最終ジャッジ日時 | 2024-06-29 23:40:02 |
合計ジャッジ時間 | 4,636 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 329 ms
369,408 KB |
testcase_01 | AC | 331 ms
369,444 KB |
testcase_02 | AC | 439 ms
369,336 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 22 ms
21,120 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 413 ms
369,356 KB |
testcase_07 | AC | 4 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 5 ms
7,424 KB |
testcase_10 | AC | 3 ms
5,376 KB |
testcase_11 | AC | 7 ms
8,704 KB |
testcase_12 | AC | 9 ms
9,728 KB |
testcase_13 | AC | 3 ms
5,376 KB |
testcase_14 | AC | 260 ms
292,608 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for (int i = 0; i < (n); ++i) #define reps(i,n) for (int i = 1; i <= (n); ++i) #define rrep(i,n) for (int i = (n) - 1; i >= 0; --i) #define rreps(i,n) for (int i = (n); i > 0; --i) #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(), (x).end() #define PB push_back #define MP make_pair #define y0 y3487465 #define y1 y8687969 #define j0 j1347829 #define j1 j234892 using namespace std; using ll = long long; using P = pair<int,int>; int str2int(string str) { int mm = (str[0] - '0') * 10 + (str[1] - '0'); int ss = (str[3] - '0') * 10 + (str[4] - '0'); return 60 * mm + ss; } const int N = 50, L = 300 * 60; int n, l, s[N]; /* i曲目まででj曲選びk秒以内である場合の数 */ ll dp[N + 1][N + 1][L + 1]; double fact_inv(int n) { double res = 1; reps(i, n) res /= i; return res; } int main() { cin >> n >> l; l *= 60; // min -> s string str_s; rep(i, n) { cin >> str_s; s[i] = str2int(str_s); } int ssm = 0; rep(i, n) ssm += s[i]; if (ssm <= l) { cout << n << endl; return 0; } rep(i, n + 1) rep(j, n + 1) rep(k, l + 1) dp[i][j][k] = 0; rep(k, l + 1) dp[0][0][k] = 1; rep(i, n) rep(j, n + 1) rep(k, l + 1) { dp[i + 1][j][k] += dp[i][j][k]; if (j - 1 >= 0 && k - s[i] >= 0) dp[i + 1][j][k] += dp[i][j - 1][k - s[i]]; } rep(i, n) rep(j, n + 1) rep(k, l + 1) { dp[i][j][k] = dp[n][j][k]; if (j - 1 >= 0 && k - s[i] >= 0) dp[i][j][k] -= dp[i][j - 1][k - s[i]]; } // rep(i, n) { // printf("i = %d\n", i); // rep(j, n + 1) { // printf("dp[%d][%d][%d] = %lld\n", i, j, l, dp[i][j][l]); // // rep(k, l + 1) printf("%lld ", dp[i][j][k]); // // printf("\n"); // } // } double ans = 0; rep(i, n) rep(j, n) { if (l - s[i] - 1 < 0) ans += dp[i][j][l - 1] * fact_inv(n - 1) / fact_inv(j) / fact_inv(n - j - 1) * (j + 1) / n; else ans += (dp[i][j][l - 1] - dp[i][j][l - s[i] - 1]) * fact_inv(n - 1) / fact_inv(j) / fact_inv(n - j - 1) * (j + 1) / n; // printf("i = %d, j = %d, ans = %.9f\n", i, j, ans); } printf("%.9f\n", ans); return 0; }