結果
問題 | No.155 生放送とBGM |
ユーザー |
|
提出日時 | 2018-07-03 01:55:17 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,593 ms / 6,000 ms |
コード長 | 2,486 bytes |
コンパイル時間 | 2,201 ms |
コンパイル使用メモリ | 79,144 KB |
実行使用メモリ | 81,416 KB |
最終ジャッジ日時 | 2024-07-01 01:53:51 |
合計ジャッジ時間 | 13,741 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
ソースコード
import java.io.BufferedReader;import java.io.File;import java.io.FileNotFoundException;import java.io.FileReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main {public static void main(String[]args) throws Throwable {double fac[] = new double[60];int maxSum = 25500;double dp1[][] = new double[maxSum + 10][60];double dp2[][] = new double[maxSum + 10][60];fac[0] = 1;for (int i = 1 ; i < 60 ; ++i) {fac[i] = 1.0*i * fac[i - 1];}int s[] = new int[60];Scanner sc = new Scanner(System.in);int n = sc.nextInt(), l = sc.nextInt();long sum = 0;l*=60;for (int i = 0 ; i < n ; ++i) {String str = sc.next();StringTokenizer st = new StringTokenizer(str,":");int x = new Integer(st.nextToken()), y= new Integer(st.nextToken());s[i]=x*60+y;sum+=s[i];}if (l >= sum) {System.out.println(n);return;}dp1[0][0] = 1;for (int i = 0 ; i < n ; ++i) {for (int j = i; j >= 0 ; --j) {for (int cur = 0; cur <= maxSum ; ++cur) {dp1[Math.min(maxSum,cur + s[i])][j + 1] += 1.0*dp1[cur][j];}}}double ways = 0.0;for (int i = 0 ; i < n ; ++i) {for (int j = 0 ; j < n ; ++j) {for (int cur = 0 ; cur < l ;++cur) {dp2[cur][j] = dp1[cur][j];if (cur - s[i] >= 0 && j >= 1) {dp2[cur][j] -= dp2[cur - s[i]][j - 1];}if (j < n && cur + s[i] >= l) {ways += 1.0*(j+1)*(((dp2[cur][j] * 1.0*fac[j] * fac[n - j - 1])));}}}}System.out.printf("%.15f\n",ways/fac[n]);}static class Scanner {StringTokenizer st;BufferedReader br;public Scanner(InputStream s) {br = new BufferedReader(new InputStreamReader(s));}public Scanner(String s) throws FileNotFoundException {br = new BufferedReader(new FileReader(new File(s)));}public String next() throws IOException {while (st == null || !st.hasMoreTokens())st = new StringTokenizer(br.readLine());return st.nextToken();}public int nextInt() throws IOException {return Integer.parseInt(next());}public long nextLong() throws IOException {return Long.parseLong(next());}public String nextLine() throws IOException {return br.readLine();}public double nextDouble() throws IOException {return Double.parseDouble(next());}public boolean ready() throws IOException {return br.ready();}}}