結果

問題 No.155 生放送とBGM
コンテスト
ユーザー kimiyuki
提出日時 2016-02-19 21:55:32
言語 C++11(old_compat)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -include bits/stdc++.h -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 335 ms / 6,000 ms
コード長 1,377 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,417 ms
コンパイル使用メモリ 176,260 KB
実行使用メモリ 20,768 KB
最終ジャッジ日時 2026-03-08 16:05:41
合計ジャッジ時間 3,846 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
typedef long long ll;
using namespace std;
int main() {
    int n, l; cin >> n >> l;
    l *= 60;
    vector<int> s(n);
    repeat (i,n) {
        int mn, sc; char dummy; cin >> mn >> dummy >> sc;
        s[i] = mn * 60 + sc;
    }
    if (accumulate(s.begin(), s.end(), 0) <= l) {
        cout << n << endl;
        return 0;
    }
    int max_s = *max_element(s.begin(), s.end());
    vector<vector<ll> > dp(n+1, vector<ll>(l+max_s));
    dp[0][0] = 1;
    repeat (i,n) {
        repeat_reverse (j,n) {
            repeat_reverse (k,l) {
                dp[j+1][k+s[i]] += dp[j][k];
            }
        }
    }
    double acc = 0;
    vector<double> fact(n+1); fact[0] = 1; repeat (i,n) fact[i+1] = (i+1) * fact[i];
    repeat (i,n) {
        vector<vector<ll> > prv = dp;
        repeat (j,n) {
            repeat (k,l) {
                prv[j+1][k+s[i]] -= prv[j][k];
            }
        }
        repeat (j,n) {
            repeat_from (k,max(0,l-s[i]),l) {
                acc += (j+1) * fact[j] * prv[j][k] * fact[n-j-1];
            }
        }
    }
    printf("%.12lf\n", acc / fact[n]);
    return 0;
}
0