結果

問題 No.155 生放送とBGM
コンテスト
ユーザー ctyl_0
提出日時 2015-11-05 15:11:38
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,142 bytes
コンパイル時間 826 ms
コンパイル使用メモリ 89,560 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-13 12:42:45
合計ジャッジ時間 1,658 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 11
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 #
raw source code 

#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) revdp[j][k] -= revdp[j - 1][k - S[i]];
                // if(revdp[j][k]) cout << "revdp[" << j << "][" << k << "] = " << revdp[j][k] << endl;
                if (k < L) ret += revdp[j][k] * fact[j] * fact[N - j - 1];
            }
        }
        
    }
    
    // output(ret, 0);
    ret /= fact[N];
    
    output(ret, 25);
    return 0;
}
0