結果

問題 No.155 生放送とBGM
ユーザー kimiyukikimiyuki
提出日時 2016-02-19 21:55:32
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,377 bytes
コンパイル時間 414 ms
コンパイル使用メモリ 59,956 KB
最終ジャッジ日時 2024-11-14 19:34:41
合計ジャッジ時間 786 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:18:9: error: ‘accumulate’ was not declared in this scope
   18 |     if (accumulate(s.begin(), s.end(), 0) <= l) {
      |         ^~~~~~~~~~

ソースコード

diff # 

#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