QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#131831#5127. Crashing Competition ComputerPetroTarnavskyi#AC ✓16ms4072kbC++171.2kb2023-07-28 14:59:272023-07-28 14:59:31

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-28 14:59:31]
  • 评测
  • 测评结果:AC
  • 用时:16ms
  • 内存:4072kb
  • [2023-07-28 14:59:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

typedef long double db; 

const int N = 1 << 12;
db f[N], pw[N], npw[N];


db calc(db p, int n){
	db res = (1 - p) * (1 - npw[n]) / p  - npw[n + 1] * n;
	return res / p;
}

db dp[N];


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, save, rest;
	cin >> n >> save >> rest;
	
	db p;
	cin >> p;
	
	pw[0] = npw[0] = 1;
	FOR(i, 1, N){
		pw[i] = pw[i - 1] * p;
		npw[i] = npw[i - 1] * (1 - p);
	}	
	FOR(len, 1, N){
		db l = npw[len];
		db r = npw[len] * len; 
		r += (rest + 1) * (1 - npw[len]);
		r += p * calc(p, len - 1);
		
		
		f[len] = r / l;
	}
	
	FOR(i, 1, n + 1){
		dp[i] = f[i];
		FOR(j, 0, i)
			dp[i] = min(dp[i], dp[j] + f[i - j]);
		dp[i] += save;
	}
	cout << fixed << setprecision(10) << dp[n] << endl;
	
	


	
	
	
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3856kb

input:

2 1 5
0.25

output:

8.0000000000

result:

ok found '8.0000000', expected '8.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

3 5 2
0.5

output:

26.0000000000

result:

ok found '26.0000000', expected '26.0000000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

10 4 5
0.327

output:

68.6649673569

result:

ok found '68.6649674', expected '68.6649674', error '0.0000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3864kb

input:

1 0 0
0.0010000000

output:

1.0010010010

result:

ok found '1.0010010', expected '1.0010010', error '0.0000000'

Test #5:

score: 0
Accepted
time: 16ms
memory: 3904kb

input:

2000 1000000000 1000000000
0.9990000000

output:

2000000001999999.9862060547

result:

ok found '2000000002000000.0000000', expected '2000000001999999.7500000', error '0.0000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3988kb

input:

1 8 3
0.2796819062

output:

10.5531022120

result:

ok found '10.5531022', expected '10.5531022', error '0.0000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

2 8 5
0.1950111999

output:

13.5014129988

result:

ok found '13.5014130', expected '13.5014130', error '0.0000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 4032kb

input:

3 16 18
0.8093709499

output:

293.0100405479

result:

ok found '293.0100405', expected '293.0100405', error '0.0000000'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3860kb

input:

5 27 5
0.1016038960

output:

37.5183273128

result:

ok found '37.5183273', expected '37.5183273', error '0.0000000'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3936kb

input:

8 20 21
0.5406174088

output:

375.1229205710

result:

ok found '375.1229206', expected '375.1229206', error '0.0000000'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3936kb

input:

13 34 11
0.6335809300

output:

724.7420335683

result:

ok found '724.7420336', expected '724.7420336', error '0.0000000'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3944kb

input:

21 52 17
0.9288548522

output:

6048.0819414785

result:

ok found '6048.0819415', expected '6048.0819415', error '0.0000000'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3860kb

input:

34 132 164
0.0295578195

output:

482.8591117164

result:

ok found '482.8591117', expected '482.8591117', error '0.0000000'

Test #14:

score: 0
Accepted
time: 0ms
memory: 4040kb

input:

55 117 318
0.7124092792

output:

49951.8362122204

result:

ok found '49951.8362122', expected '49951.8362122', error '0.0000000'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3836kb

input:

89 116 459
0.7984980681

output:

172647.2307082069

result:

ok found '172647.2307082', expected '172647.2307082', error '0.0000000'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3836kb

input:

144 741 736
0.7150041760

output:

373104.4037798954

result:

ok found '373104.4037799', expected '373104.4037799', error '0.0000000'

Test #17:

score: 0
Accepted
time: 1ms
memory: 4044kb

input:

233 127 974
0.7710504851

output:

794898.3179303085

result:

ok found '794898.3179303', expected '794898.3179303', error '0.0000000'

Test #18:

score: 0
Accepted
time: 1ms
memory: 3880kb

input:

377 1681 979
0.3568400567

output:

551765.6624942877

result:

ok found '551765.6624943', expected '551765.6624943', error '0.0000000'

Test #19:

score: 0
Accepted
time: 2ms
memory: 3888kb

input:

610 1235 115
0.8676943978

output:

1218022.4022519887

result:

ok found '1218022.4022520', expected '1218022.4022520', error '0.0000000'

Test #20:

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

input:

987 4032 5649
0.7936064850

output:

25423038.5306622400

result:

ok found '25423038.5306622', expected '25423038.5306620', error '0.0000000'

Test #21:

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

input:

1597 3431 3413
0.5147094423

output:

11263578.2329618653

result:

ok found '11263578.2329619', expected '11263578.2329617', error '0.0000000'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

10 414476469 201924720
0.5576732524

output:

6223036669.4392874772

result:

ok found '6223036669.4392872', expected '6223036669.4392872', error '0.0000000'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

100 407636752 720532711
0.5673348171

output:

135243959485.8359700367

result:

ok found '135243959485.8359680', expected '135243959485.8356476', error '0.0000000'

Test #24:

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

input:

1000 240030668 25521919
0.6307096382

output:

200826696696.3158021122

result:

ok found '200826696696.3157959', expected '200826696696.3182678', error '0.0000000'

Test #25:

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

input:

2000 972602846 455481132
0.8198257434

output:

6090250224922.1747159958

result:

ok found '6090250224922.1748047', expected '6090250224922.0097656', error '0.0000000'

Test #26:

score: 0
Accepted
time: 1ms
memory: 3928kb

input:

10 825212410 251246434
0.0083164428

output:

847095595.1788395941

result:

ok found '847095595.1788396', expected '847095595.1788396', error '0.0000000'

Test #27:

score: 0
Accepted
time: 1ms
memory: 3860kb

input:

100 899786066 372335720
0.0094461482

output:

1489340921.1314813818

result:

ok found '1489340921.1314814', expected '1489340921.1314816', error '0.0000000'

Test #28:

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

input:

1000 231215859 902529138
0.0092594791

output:

15086975240.7109708982

result:

ok found '15086975240.7109718', expected '15086975240.7110081', error '0.0000000'

Test #29:

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

input:

2000 922013265 142267051
0.0031002828

output:

5721795022.7732246346

result:

ok found '5721795022.7732248', expected '5721795022.7731447', error '0.0000000'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

10 992256325 66321807
0.9944521019

output:

128803372133.1987262592

result:

ok found '128803372133.1987305', expected '128803372133.1986084', error '0.0000000'

Test #31:

score: 0
Accepted
time: 1ms
memory: 3960kb

input:

100 265647836 244754334
0.9945243461

output:

4471954310072.6464285851

result:

ok found '4471954310072.6464844', expected '4471954310072.6093750', error '0.0000000'

Test #32:

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

input:

1000 238380436 864562324
0.9902479885

output:

88028586925592.9710464478

result:

ok found '88028586925592.9687500', expected '88028586925593.4531250', error '0.0000000'

Test #33:

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

input:

2000 521552414 462178693
0.9909631873

output:

102406735329587.8447647095

result:

ok found '102406735329587.8437500', expected '102406735329591.2343750', error '0.0000000'

Test #34:

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

input:

1597 4157 690
0.4523019984

output:

4088184.5295214221

result:

ok found '4088184.5295214', expected '4088184.5295214', error '0.0000000'

Test #35:

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

input:

2000 661541596 520442869
0.9934464406

output:

159109740849730.8762512207

result:

ok found '159109740849730.8750000', expected '159109740849727.9687500', error '0.0000000'

Test #36:

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

input:

2000 486845603 424498022
0.6864549247

output:

2832427200807.1169738770

result:

ok found '2832427200807.1171875', expected '2832427200807.0190430', error '0.0000000'