結果
問題 | No.155 生放送とBGM |
ユーザー | beet |
提出日時 | 2019-03-26 17:47:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 804 ms / 6,000 ms |
コード長 | 1,819 bytes |
コンパイル時間 | 2,448 ms |
コンパイル使用メモリ | 205,640 KB |
最終ジャッジ日時 | 2025-01-07 00:32:06 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:29:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 29 | scanf("%d %d",&n,&l); | ~~~~~^~~~~~~~~~~~~~~ main.cpp:35:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 35 | scanf("%02d:%02d ",&x,&y); | ~~~~~^~~~~~~~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} template<typename T> vector<T> make_v(size_t a){return vector<T>(a);} template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts){ return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;} template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){ for(auto &e:t) fill_v(e,v); } //INSERT ABOVE HERE signed main(){ int n,l; scanf("%d %d",&n,&l); l*=60; vector<int> v(n); int sum=0; for(int i=0;i<n;i++){ int x,y; scanf("%02d:%02d ",&x,&y); v[i]=x*60+y; sum+=v[i]; } if(sum<=l){ cout<<n<<endl; return 0; } using D = long double; auto dp=make_v<D>(2,n+1,l+1); vector<D> fact(n+1,1); for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i; D ans=0; fill_v(dp[0],0); dp[0][0][0]=1; for(int i=0;i<n;i++){ int f=i&1; fill_v(dp[!f],0); for(int j=0;j<n;j++){ for(int k=0;k<l;k++){ dp[!f][j][k]+=dp[f][j][k]; if(k+v[i]<l) dp[!f][j+1][k+v[i]]+=dp[f][j][k]; } } } { for(int t=0;t<n;t++){ int i=n; int f=i&1; fill_v(dp[!f],0); for(int j=0;j<n;j++){ for(int k=0;k<l;k++){ dp[!f][j][k]=dp[f][j][k]; if(j>=1&&k>=v[t]) dp[!f][j][k]-=dp[!f][j-1][k-v[t]]; if(k+v[t]>=l) ans+=dp[!f][j][k]*(j+1)*fact[j]*fact[n-(j+1)]; } } } } printf("%.12Lf\n",ans/fact[n]); return 0; }