結果
問題 | No.155 生放送とBGM |
ユーザー | MorikiN |
提出日時 | 2020-05-28 11:16:07 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 7,671 bytes |
コンパイル時間 | 1,935 ms |
コンパイル使用メモリ | 182,588 KB |
実行使用メモリ | 35,384 KB |
最終ジャッジ日時 | 2024-10-13 04:04:55 |
合計ジャッジ時間 | 3,922 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | AC | 12 ms
27,776 KB |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | AC | 11 ms
27,944 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | AC | 14 ms
28,416 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
ソースコード
#include <bits/stdc++.h> #include <algorithm> #include <cmath> #include <set> #include <cstdio> #include <vector> #include <iostream> #include <utility> #include <queue> #include <map> #include <complex> #define fir first #define sec second #define sz(s) (s).size() #define pb push_back #define get(n) scanf("%d",&n); #define gets(s) string s;cin >> (s); #define prfi(n) printf("%d", &n); #define prfd(n) printf("%lf", &n); #define All(s) (s).begin(), (s).end() #define rep(i,j) for(int (i)=0;(i)<(j);(i)++) #define For(i,j,k) for(int (i)=(j);(i)<(k);(i)++) #define drep(i,j) for(int (i)=(j);(i)>=0;(i)--) #define Ford(i,j,k) for(int (i)=(j);i>=(k);i--) #define fore(c,v) for(auto (c): (v)) #define lp for(int __=0;__<n;i++) #define mem(a,b) memset(a,b,sizeof(a)); #define dump(x) std::cout << #x << " = " << (x) << std::endl; #define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; using ull = unsigned long long int; using ll = long long; using ld = long double; using pii = std::pair<int,int>; using pll = std::pair<ll, ll>; using vi = std::vector<int> ; using vvi = std::vector<vi> ; using vll = std::vector<ll>; using vvll = std::vector<vll>; using vd = std::vector<double> ; using vvd = std::vector<vd> ; using qi = std::queue<int> ; using vpii = std::vector<std::pair<int, int> >; using vpll = std::vector<pll>; using namespace std; const int Mod = (1e9) + 7; const int INF = 1e9 + 19; const ll INFL = 1e18 + 19; const int dx[] = {-1, 0, 0, 1}; const int dy[] = {0, -1, 1, 0}; const int dx2[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1}; const int dy2[] = {1, 0, -1, 1, 0, -1, 1, 0, -1}; const double EPS = 1e-10; //_____________________________________Templates_________________________________________// template<class T1, class T2> inline void chmin(T1 &a, T2 b){if(a > b) a = b;} template<class T1, class T2> inline void chmax(T1 &a, T2 b){if(a < b) a = b;} template<class T> inline void pri(T a){cout << a << endl;} template<class Z> using vec = vector<Z>; template<class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>; //mainly use for dynamic prog template<class T1, class T2> void update(T1 &a, T2 b){ a += b; if(a > Mod) a %= Mod; } inline void IN(void){ return; } template <typename First, typename... Rest> void IN(First& first, Rest&... rest){ cin >> first; IN(rest...); return; } inline void OUT(void){ cout << "\n"; return; } template <typename First, typename... Rest> void OUT(First first, Rest... rest){ cout << first << " "; OUT(rest...); return; } bool pairsort(pll pl, pll pr){ if(pl.first == pr.first)return pl.second > pr.second; return pl.first < pr.first; } int cntbit(ll a,int n,int j){int res = 0;For(i,j,n){if(a>>i & 1){res++;}}return res;} vector<int> make_bit(int a){vector<int> res; for(int i=31;i>=0;i--)if(a&(1<<i))res.pb(i);return res;} bool stdbit(int a, int b){return a&(1 << b); } int GCD(int a, int b){if(b > a)return GCD(b,a);if(a%b == 0)return b;else return GCD(b, a%b);} int LCM(int a, int b){return a*b/GCD(a,b);} int roundup(int a, int b){if(a % b == 0)return a/b;else return (a+b)/b;} int rounddown(int a, int b){if(a%b == 0)return a/b;else {return (a-b)/b;}} ll pow(ll a, ll n){ll res = 1;while(n > 0){if(n&1)res *= a; a *= a; n = n >> 1;}return res;} ll GetDiviserCount(ll N)//約数の個数 { ll res = 1; For(i,2,sqrt(N)+1) { ll cnt = 0; while(N%i == 0) { cnt++; N /= i; } res *= (cnt + 1); if(N == 1)break; } if(N != 1)res *= 2; return res; } vll GetDivisor(ll N)//約数列挙 { vll res; for(ll i = 1;i*i <= N;i++) { if(N%i == 0) { res.pb(i); if(i*i != N)res.pb(N/i); } } sort(All(res)); return res; } struct mint { ll x; // typedef long long ll; mint(ll x=0):x((x%Mod+Mod)%Mod){} mint operator-() const { return mint(-x);} mint& operator+=(const mint a) { if ((x += a.x) >= Mod) x -= Mod; return *this; } mint& operator-=(const mint a) { if ((x += Mod-a.x) >= Mod) x -= Mod; return *this; } mint& operator*=(const mint a) { (x *= a.x) %= Mod; return *this; } mint operator+(const mint a) const { mint res(*this); return res+=a; } mint operator-(const mint a) const { mint res(*this); return res-=a; } mint operator*(const mint a) const { mint res(*this); return res*=a; } mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; } // for prime mod mint inv() const { return pow(Mod-2); } mint& operator/=(const mint a) { return (*this) *= a.inv(); } mint operator/(const mint a) const { mint res(*this); return res/=a; } friend ostream& operator<<(ostream& os, const mint& a); }; ostream& operator<<(ostream& os, const mint& a) { os << a.x; return os; } using vm = vector<mint>; using vvm = vector<vm>; struct combination { vector<mint> fact, ifact; combination(int n):fact(n+1),ifact(n+1) { assert(n < Mod); fact[0] = 1; for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i; ifact[n] = fact[n].inv(); for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i; } mint operator()(int n, int k) { if (k < 0 || k > n) return 0; return fact[n]*ifact[k]*ifact[n-k]; } }; template<class Z> struct MyMatrix { using mat = MyMatrix<Z>; vector<vector<Z>> m_dat; int m_h; int m_w; MyMatrix(int h, int w) : m_h(h), m_w(w) ,m_dat(h,vector<Z>(w)) {} vector<Z> &operator[] (int idx) { return m_dat[idx]; } mat Multiple(mat &a) { mat C(m_h, a.m_w); for(int i=0;i<m_h;i++) { for(int j=0;j<a.m_w;j++) { for(int k=0;k<m_w;k++) { C[i][j] += m_dat[i][k] * a[k][j]; } } } return C; } mat Pow(ll x) { mat B(m_h,m_w); for(int i=0;i<m_h;i++) { B[i][i] = 1; } mat A = *this; while(x > 0) { if(x&1)B = B.Multiple(A); A = A.Multiple(A); x = x >> 1; } return B; } //friend ostream& operator<<(ostream &os, const mat &A); }; /* template<class Z> ostream& operator<<(ostream &os, Matrix<Z>& A) { for(int i=0;i<A.m_h;i++) { for(int j=0;j<A.m_w;j++) { os << A[i][j] << " "; } os << endl; } return os; } */ template<class T> using mat = MyMatrix<T>; //_____________________ following sorce code_________________________// const int max_n = 3 * (1e5) + 1; const int max_m = 83 * (1e5) + 1; int n,m,k; ll N; int h,w; string S; int a,b,c; vi v; int ans; double x,y,z; vector<int> G[1010101]; signed main (int argc, char* argv[]) { cin.tie(0); ios::sync_with_stdio(false); const int Max = 20202; int l; IN(n,l); l *= 60; vi t(n); int sum = 0; rep(i,n) { scanf("%d:%d",&a,&b); t[i] = a*60 + b; //dump(t[i]); sum += t[i]; } vvi dp(n+1,vi(Max+1)); dp[0][0] = 1; rep(i,n) { drep(j,i) { rep(k,Max+1) { dp[j+1][min(Max+1,k+t[i])] += dp[j][k]; } } } /* rep(j,n) { rep(k,Max) { if(dp[j+1][k])cout << "dp[" << j+1 << "][" << k << "] = " << dp[j+1][k] << endl; } } */ double ans = 0; double fact[80]; fact[0] = fact[1] = 1.0; For(i,2,80) { fact[i] = fact[i-1]*i; } vvi T(n+1,vi(Max+1)); rep(i,n) { rep(j,n) { rep(k,l) { T[j][k] = dp[j][k]; if(j > 0 and k >= t[i])T[j][k] -= T[j-1][k-t[i]]; ans += T[j][k] * (fact[j] * fact[n-1-j]); } } } ans /= fact[n]; //pri(ans); //for(auto c : ans){cout << c << endl;} cout << fixed << setprecision(15) << ans << endl; return 0; }