結果

問題 No.155 生放送とBGM
ユーザー はまやんはまやん
提出日時 2019-02-06 22:36:32
言語 C++14
(gcc 8.3.0)
結果
AC  
実行時間 2,683 ms
コード長 2,437 Byte
コンパイル時間 1,312 ms
使用メモリ 219,528 KB
最終ジャッジ日時 2019-09-06 02:06:16

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1.txt AC 2,653 ms
219,528 KB
2.txt AC 2,648 ms
219,524 KB
3.txt AC 2,683 ms
219,524 KB
4.txt AC 2,654 ms
219,524 KB
5.txt AC 994 ms
134,052 KB
6.txt AC 10 ms
7,280 KB
7.txt AC 2,638 ms
219,512 KB
system_test1.txt AC 39 ms
22,940 KB
system_test2.txt AC 22 ms
14,396 KB
system_test3.txt AC 62 ms
31,488 KB
system_test4.txt AC 30 ms
18,672 KB
system_test5.txt AC 61 ms
31,488 KB
system_test6.txt AC 78 ms
35,764 KB
system_test7.txt AC 49 ms
27,216 KB
system_test8.txt AC 2,359 ms
206,712 KB
テストケース一括ダウンロード

ソースコード

diff #
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧  
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     
    /   \     | |     
    /   / ̄ ̄ ̄ ̄/  |  
  __(__ニつ/     _/ .| .|____  
     \/____/ (u ⊃  
---------------------------------------------------------------------------------------------------*/






int N, L, A[50];
double dp[2][51][301010];
double dp2[51][301010];
double fact[51];
//---------------------------------------------------------------------------------------------------
void _main() {
    scanf("%d %d", &N, &L);
    rep(i, 0, N) {
        int m, s;
        scanf("%d:%d", &m, &s);
        A[i] = m * 60 + s;
    }
    L *= 60;

    fact[0] = 1;
    rep(i, 1, 51) fact[i] = fact[i - 1] * i;

    dp[0][0][0] = 1;
    rep(i, 0, N) {
        int cur = i % 2;
        int nxt = 1 - cur;
        rep(cnt, 0, N + 1) rep(l, 0, 181818) {
            dp[nxt][cnt][l] = dp[cur][cnt][l];
            if (0 <= cnt - 1 and 0 <= l - A[i]) dp[nxt][cnt][l] += dp[cur][cnt - 1][l - A[i]];
        }
    }

    // dp[nxt][cnt][l] = dp[pre][cnt][l] + dp[pre][cnt-1][l-A[i]]
    // dp[pre][cnt][l] = dp[nxt][cnt][l] - dp[pre][cnt-1][l-A[i]]

    double ans = 0;
    rep(i, 0, N) {
        rep(cnt, 0, N + 1) rep(l, 0, 181818) {
            dp2[cnt][l] = dp[N%2][cnt][l];
            if (0 <= cnt - 1 and 0 <= l - A[i]) dp2[cnt][l] -= dp2[cnt - 1][l - A[i]];
        }
        rep(cnt, 0, N) rep(l, 0, L) ans += fact[cnt] * fact[N - cnt - 1] * dp2[cnt][l];
    }
    ans /= fact[N];

    printf("%.10f\n", ans);
}
0