結果

問題 No.155 生放送とBGM
ユーザー ctyl_0ctyl_0
提出日時 2015-11-05 15:43:50
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 154 ms / 6,000 ms
コード長 2,137 bytes
コンパイル時間 734 ms
コンパイル使用メモリ 88,300 KB
実行使用メモリ 26,260 KB
最終ジャッジ日時 2024-09-13 12:44:18
合計ジャッジ時間 2,239 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 150 ms
22,816 KB
testcase_01 AC 146 ms
22,808 KB
testcase_02 AC 154 ms
26,260 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 10 ms
14,788 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 134 ms
18,352 KB
testcase_07 AC 3 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 4 ms
8,424 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 4 ms
8,196 KB
testcase_12 AC 4 ms
8,144 KB
testcase_13 AC 3 ms
7,872 KB
testcase_14 AC 114 ms
22,132 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:64:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   64 |         scanf("%d:%d", &m, &s);
      |         ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define var auto
#define mod 1000000007
#define inf 2147483647
#define nil -1
typedef long long ll;

using namespace std;

int inputValue(){
    int a;
    cin >> a;
    return a;
}

template <typename T>
void output(T a, int precision) {
    if(precision > 0){
        cout << fixed << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

// end of template

double fact[51];
double dp[51][36001];
double revdp[51][36001];

int main() {
    cin.tie(0);
//    ios_base::sync_with_stdio(false);
    // source code
    
    // calculate n!
    fact[0] = 1;
    repd(i, 1, 51){
        fact[i] = fact[i - 1] * i;
    }
    
    int N = inputValue(); // 50
    int L = inputValue() * 60; // second 300 * 60 = 18000
    vector<int> S(N); // second // 00:01 ~ 59:59
    int sum = 0;
    rep(i, N){
        int m, s;
        scanf("%d:%d", &m, &s);
        S[i] = min(L, m * 60 + s);
        sum += S[i];
    }
    
    if (sum <= L) {
        output(N, 0);
        return 0;
    }
    
    dp[0][0] = 1;
    rep(i, N){
        for (int j = i; j >= 0; j--) {
            for (int k = 0; S[i] + k <= 2 * L; k++) {
                if (dp[j][k]){
                    dp[j + 1][k + S[i]] += dp[j][k];
                }
            }
        }
    }
    
    // 戻すDP
    double ret = 0;
    
    rep(i, N){
        rep(j, N){
            for (int k = 0; k < L + S[i]; k++) {
                revdp[j][k] = dp[j][k];
                if (k - S[i] >= 0 && j > 0) revdp[j][k] -= revdp[j - 1][k - S[i]];
                if (k < L) ret += revdp[j][k] * fact[j] * fact[N - j - 1];
            }
        }
        
    }
    
    // output(ret, 0);
    
//    for (int i = N; i >= 1; i--) {
//        ret /= i;
//    }
    ret /= fact[N];
    printf("%.14f", ret);
    //output(ret, 25);
    return 0;
}
0