結果

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

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1.txt AC 2,012 ms
338,500 KB
2.txt AC 2,007 ms
338,504 KB
3.txt AC 2,019 ms
338,504 KB
4.txt AC 2,005 ms
338,504 KB
5.txt AC 724 ms
222,140 KB
6.txt AC 7 ms
11,192 KB
7.txt AC 2,009 ms
338,492 KB
system_test1.txt AC 22 ms
37,812 KB
system_test2.txt AC 11 ms
23,480 KB
system_test3.txt AC 37 ms
52,152 KB
system_test4.txt AC 17 ms
31,668 KB
system_test5.txt AC 36 ms
52,152 KB
system_test6.txt AC 47 ms
58,292 KB
system_test7.txt AC 28 ms
43,960 KB
system_test8.txt AC 1,795 ms
326,336 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