QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#225004 | #2897. Circle Bounce | PetroTarnavskyi# | TL | 0ms | 0kb | C++17 | 1.4kb | 2023-10-23 20:23:26 | 2023-10-23 20:23:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long double db;
const int N = 55;
const int T = 2505;
int tim[N];
db p[N];
db dp[N][N][T];
db CDP[N][N];
db C(int n, int k)
{
if(CDP[n][k] > 0.5)
return CDP[n][k];
db res = 1;
FOR(i, 0, k)
{
res *= (n - i) / (i + 1);
}
return CDP[n][k] = res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
int n, K, t;
cin >> n >> K >> t;
FOR(i, 0, n)
{
cin >> p[i] >> tim[i];
}
VI order(n);
iota(ALL(order), 0);
sort(ALL(order), [&](int i, int j){return tim[i] < tim[j];});
dp[0][0][0] = 1;
vector<db> ans(n);
FOR(it, 0, n)
{
int i = order[it];
FOR(k, 0, min(it + 1, K))
{
FOR(ti, 0, t + 1)
{
dp[it + 1][k][ti] += dp[it][k][ti];
if(ti + tim[i] <= t)
dp[it + 1][k + 1][ti + tim[i]] += p[i] * dp[it][k][ti];
dp[it + 1][k + 1][ti] += (1 - p[i]) * dp[it][k][ti];
ans[i] += p[i] * dp[it][k][ti] * C(n - it - 1, K - k - 1) / C(n - 1, K - 1);
}
}
}
FOR(i, 0, n)
cout << ans[i] << "\n";
return 0;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
999999998 999999999 1000000000