結果
問題 | No.155 生放送とBGM |
ユーザー |
|
提出日時 | 2018-07-12 17:02:22 |
言語 | D (dmd 2.109.1) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,318 bytes |
コンパイル時間 | 2,519 ms |
コンパイル使用メモリ | 153,600 KB |
実行使用メモリ | 745,260 KB |
最終ジャッジ日時 | 2024-06-13 01:26:51 |
合計ジャッジ時間 | 8,807 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 8 WA * 1 RE * 1 MLE * 5 |
ソースコード
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;auto rdsp(){return readln.splitter;}void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}void readA(T)(size_t n,ref T[]t){t=new T[](n);auto r=rdsp;foreach(ref v;t)pick(r,v);}void main(){int n, l; readV(n, l);string[] st; readA(n, st);l *= 60;auto s = st.map!(sti => sti[0..2].to!int*60+sti[3..5].to!int).array;if (s.sum < l) {writeln(n);return;}auto dp1 = new long[][][](n+1, n+1, l); dp1[0][0][0] = 1;foreach (i; 0..n)foreach (j; 0..n+1)foreach (k; 0..l) {dp1[i+1][j][k] = dp1[i][j][k];if (j >= 1 && k >= s[i])dp1[i+1][j][k] += dp1[i][j-1][k-s[i]];}auto dp2 = new long[][][](n, n+1, l);foreach (i; 0..n)foreach (j; 0..n+1)foreach (k; 0..l) {dp2[i][j][k] = dp1[n][j][k];if (j >= 1 && k >= s[i])dp2[i][j][k] -= dp2[i][j-1][k-s[i]];}auto fact = new real[](n+1); fact[0] = 1;foreach (i; 1..n+1) fact[i] = fact[i-1]*i;auto r = 0.0L;foreach (i; 0..n)foreach (j; 0..n)foreach (k; l-s[i]..l)r += dp2[i][j][k]*fact[j+1]*fact[n-1-j];writefln("%.10f", r/fact[n]);}