QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#225004#2897. Circle BouncePetroTarnavskyi#TL 0ms0kbC++171.4kb2023-10-23 20:23:262023-10-23 20:23:27

Judging History

This is the latest submission verdict.

  • [2023-10-23 20:23:27]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2023-10-23 20:23:26]
  • Submitted

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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

999999998 999999999 1000000000

output:


result: