QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227313#6801. BlackjackjzhTL 15ms11752kbC++231.2kb2023-10-27 12:05:092023-10-27 12:05:09

Judging History

你现在查看的是最新测评结果

  • [2023-10-27 12:05:09]
  • 评测
  • 测评结果:TL
  • 用时:15ms
  • 内存:11752kb
  • [2023-10-27 12:05:09]
  • 提交

answer

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx2","sse2","fma")
#include<bits/stdc++.h>

using namespace std;

using db = __float128;

const int maxn = 505;
db dp[maxn][maxn], ndp[maxn][maxn];
int vec[maxn];

void solve() {
	int n, a, b; cin >> n >> a >> b;
	for(int i = 1 ; i <= n ; i ++) cin >> vec[i];

	dp[0][0] = 1;

	for(int i = 1 ; i <= n ; i ++) {
		memset(ndp, 0, sizeof(ndp));
		for(int x = 0 ; x < i ; x ++) {
			for(int y = 0 ; y <= b ; y ++) {
				ndp[x][y] += dp[x][y];
			}
			for(int y = 0 ; y <= b-vec[i] ; y ++) {
				ndp[x+1][y + vec[i]] += dp[x][y] * (x+1) / (n-x);
			}
		}
		memcpy(dp, ndp, sizeof(ndp));
	}

	db ans = 0;
	for(int i = 1 ; i <= n ; i ++) {
		memcpy(ndp, dp, sizeof(dp));
		for(int x = 0 ; x < n ; x ++) {
			for(int y = 0 ; y <= b-vec[i] ; y ++) {
				ndp[x+1][y+vec[i]] -= ndp[x][y] * (x+1) / (n-x);
			}
		}
		db temp = 0;
		for(int x = 0 ; x <= n-1 ; x ++) {
			for(int y = 0 ; y <= a ; y ++) {
				if(y+vec[i]>a and y+vec[i]<=b) {
					temp += ndp[x][y] / (n-x);
				}
			}
		}
		ans += temp;
	}
	cout << fixed << setprecision(50) << (long double)ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	solve();

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 11740kb

input:

5 2 4
1 1 1 5 5

output:

0.10000000000000000000135525271560688054250931600109

result:

ok found '0.1000000', expected '0.1000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 6ms
memory: 11744kb

input:

5 2 4
1 1 1 3 5

output:

0.44999999999999999998915797827514495565992547199130

result:

ok found '0.4500000', expected '0.4500000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 11ms
memory: 11620kb

input:

18 10 11
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

output:

0.00000000000000000000000000000000000000000000000000

result:

ok found '0.0000000', expected '-0.0000000', error '-0.0000000'

Test #4:

score: 0
Accepted
time: 8ms
memory: 11748kb

input:

14 15 16
3 3 3 3 3 3 3 3 3 3 3 3 3 3

output:

0.00000000000000000000000000000000000000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #5:

score: 0
Accepted
time: 3ms
memory: 11568kb

input:

7 20 23
4 4 4 4 4 4 4

output:

0.00000000000000000000000000000000000000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #6:

score: 0
Accepted
time: 10ms
memory: 11624kb

input:

10 25 27
5 5 5 5 5 5 5 5 5 5

output:

0.00000000000000000000000000000000000000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #7:

score: 0
Accepted
time: 3ms
memory: 11584kb

input:

6 30 35
6 6 6 6 6 6

output:

0.00000000000000000000000000000000000000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #8:

score: 0
Accepted
time: 4ms
memory: 11676kb

input:

9 35 36
7 7 7 7 7 7 7 7 7

output:

0.00000000000000000000000000000000000000000000000000

result:

ok found '0.0000000', expected '-0.0000000', error '-0.0000000'

Test #9:

score: 0
Accepted
time: 6ms
memory: 11740kb

input:

14 33 40
8 8 8 8 8 8 8 8 8 8 8 8 8 8

output:

1.00000000000000000000000000000000000000000000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #10:

score: 0
Accepted
time: 7ms
memory: 11504kb

input:

7 43 45
9 9 9 9 9 9 9

output:

1.00000000000000000000000000000000000000000000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #11:

score: 0
Accepted
time: 3ms
memory: 11752kb

input:

7 49 50
10 10 10 10 10 10 10

output:

1.00000000000000000000000000000000000000000000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #12:

score: 0
Accepted
time: 3ms
memory: 11628kb

input:

7 49 55
11 11 11 11 11 11 11

output:

1.00000000000000000000000000000000000000000000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #13:

score: 0
Accepted
time: 15ms
memory: 11504kb

input:

16 53 60
12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12

output:

1.00000000000000000000000000000000000000000000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #14:

score: 0
Accepted
time: 15ms
memory: 11620kb

input:

16 53 65
13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13

output:

1.00000000000000000000000000000000000000000000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #15:

score: 0
Accepted
time: 7ms
memory: 11740kb

input:

10 55 60
8 2 8 10 8 8 1 2 8 10

output:

0.56388888888888888888768421980834943951776949688792

result:

ok found '0.5638889', expected '0.5638889', error '0.0000000'

Test #16:

score: 0
Accepted
time: 4ms
memory: 11740kb

input:

10 38 43
5 8 1 9 7 2 1 9 3 1

output:

0.48888888888888888889852624153320448385784402489662

result:

ok found '0.4888889', expected '0.4888889', error '0.0000000'

Test #17:

score: 0
Accepted
time: 7ms
memory: 11664kb

input:

10 49 52
8 2 8 10 6 2 10 5 1 5

output:

0.38611111111111111110147375846679551614215597510338

result:

ok found '0.3861111', expected '0.3861111', error '0.0000000'

Test #18:

score: 0
Accepted
time: 3ms
memory: 11624kb

input:

10 44 49
3 10 3 2 7 5 5 10 5 4

output:

0.67777777777777777778621046134155392337561352178454

result:

ok found '0.6777778', expected '0.6777778', error '0.0000000'

Test #19:

score: 0
Accepted
time: 5ms
memory: 11580kb

input:

10 54 58
5 9 8 2 4 3 8 7 7 6

output:

0.30000000000000000001084202172485504434007452800870

result:

ok found '0.3000000', expected '0.3000000', error '0.0000000'

Test #20:

score: 0
Accepted
time: 10ms
memory: 11528kb

input:

10 46 49
2 2 3 9 9 3 4 5 7 7

output:

0.50000000000000000000000000000000000000000000000000

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #21:

score: 0
Accepted
time: 6ms
memory: 11624kb

input:

10 50 51
10 9 10 4 8 2 1 1 2 10

output:

0.05753968253968253968345394032402051465169279254042

result:

ok found '0.0575397', expected '0.0575397', error '0.0000000'

Test #22:

score: 0
Accepted
time: 3ms
memory: 11580kb

input:

10 35 39
8 6 4 1 3 1 9 6 2 3

output:

0.58888888888888888886600017635863935083762044087052

result:

ok found '0.5888889', expected '0.5888889', error '0.0000000'

Test #23:

score: 0
Accepted
time: 10ms
memory: 11620kb

input:

10 62 64
10 8 7 4 4 7 10 10 8 1

output:

0.04444444444444444444316448354637127948763009044342

result:

ok found '0.0444444', expected '0.0444444', error '0.0000000'

Test #24:

score: 0
Accepted
time: 9ms
memory: 11700kb

input:

10 40 41
2 2 2 4 6 4 4 6 5 10

output:

0.36666666666666666667389468114990336289338301867247

result:

ok found '0.3666667', expected '0.3666667', error '0.0000000'

Test #25:

score: -100
Time Limit Exceeded

input:

500 392 500
21 90 87 268 118 213 27 34 32 41 186 21 116 237 110 219 115 117 118 407 298 123 111 170 273 451 273 206 122 333 249 85 53 414 254 71 305 2 287 370 440 397 158 471 406 425 161 200 355 338 44 421 27 132 236 439 428 353 22 125 269 208 373 130 213 272 403 203 60 127 378 126 383 417 320 439 9...

output:


result: