結果
問題 |
No.155 生放送とBGM
|
ユーザー |
|
提出日時 | 2025-07-24 19:34:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,243 bytes |
コンパイル時間 | 2,455 ms |
コンパイル使用メモリ | 204,632 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2025-07-24 19:34:31 |
合計ジャッジ時間 | 5,528 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 13 RE * 2 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,L; cin >> N >> L; L *= 60; vector<int> A(N); int sum = 0; for(auto &a : A){ string s; cin >> s; a += (s.at(0)-'0')*600; a += (s.at(1)-'0')*60; a += (s.at(3)-'0')*10; a += (s.at(4)-'0'); sum += a; } if(sum <= L){cout << N << endl; return 0;} vector<vector<long long>> dp(N+1,vector<long long>(L)); dp.at(0).at(0) = 1; for(auto a : A){ for(int i=N-1; i>=0; i--) for(int k=0; k<L-a; k++) dp.at(i+1).at(k+a) += dp.at(i).at(k); } double answer = 0; for(auto a : A){ for(int i=1; i<=N; i++) for(int k=a; k<L; k++) dp.at(i).at(k) -= dp.at(i-1).at(k-a); for(int i=0; i<N; i++) for(int k=L-a; k<L; k++) if(dp.at(i).at(k) != 0){ double p = dp.at(i).at(k); for(int x=1; x<=i; x++) p *= x; for(int x=1; x<=N-1-i; x++) p *= x; answer += p*(i+1); } for(int i=N-1; i>=0; i--) for(int k=0; k<L-a; k++) dp.at(i+1).at(k+a) += dp.at(i).at(k); } for(int i=1; i<=N; i++) answer /= i; cout << fixed << setprecision(20) << answer << endl; }