QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#468437#4994. Graduation GuaranteeSinhoMoemeAC ✓160ms392448kbC++23701b2024-07-08 20:47:102024-07-08 20:47:10

Judging History

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

  • [2024-07-08 20:47:10]
  • 评测
  • 测评结果:AC
  • 用时:160ms
  • 内存:392448kb
  • [2024-07-08 20:47:10]
  • 提交

answer

#include<cstdio>
#include<algorithm>
using std::sort;
using std::max;
inline bool cmp(double x,double y){
	return x>y;
}
constexpr size_t MAX=(size_t)5e3;
int n,k;
double p[MAX+1],dp[MAX+1][(MAX<<1)+1],tmp,ans=0;
inline void init(){
	for(int i=0;i<=MAX;++i) for(int j=0;j<MAX<<1;++j) dp[i][j]=0;
	dp[0][MAX]=1;
	return;
}
int main(){
	init();
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i) scanf("%lf",p+i);
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;++i){
		tmp=0;
		for(int j=0;j<=MAX<<1;++j){
			if(j) dp[i][j]+=dp[i-1][j-1]*p[i];
			if(j<MAX<<1) dp[i][j]+=dp[i-1][j+1]*(1-p[i]);
			if(j>=MAX+k) tmp+=dp[i][j];
		}
		ans=max(ans,tmp);
	}
	printf("%.7lf",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 11ms
memory: 392380kb

input:

3 3
0.5 0.5 0.5

output:

0.1250000

result:

ok found '0.1250000', expected '0.1250000', error '0.0000000'

Test #2:

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

input:

4 1
0.9 0.5 0.9 0.9

output:

0.9720000

result:

ok found '0.9720000', expected '0.9720000', error '0.0000000'

Test #3:

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

input:

10 5
0.692688 0.899145 0.65621 0.936872 0.879521 0.944595 0.551165 0.661595 0.508139 0.911566

output:

0.7261704

result:

ok found '0.7261704', expected '0.7261704', error '0.0000000'

Test #4:

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

input:

100 47
0.612726 0.62994 0.675499 0.998664 0.779532 0.549285 0.80413 0.701691 0.871286 0.782539 0.677336 0.8622 0.876787 0.574809 0.675061 0.94617 0.516776 0.528521 0.748959 0.503633 0.706856 0.825646 0.682937 0.692507 0.765989 0.860494 0.660668 0.56025 0.719626 0.945801 0.512379 0.803646 0.848648 0....

output:

0.5373724

result:

ok found '0.5373724', expected '0.5373724', error '0.0000000'

Test #5:

score: 0
Accepted
time: 23ms
memory: 392408kb

input:

1 1
0.744983

output:

0.7449830

result:

ok found '0.7449830', expected '0.7449830', error '0.0000000'

Test #6:

score: 0
Accepted
time: 103ms
memory: 392404kb

input:

5000 1
0.506147 0.719663 0.733941 0.962763 0.600348 0.705419 0.834251 0.871054 0.769358 0.846804 0.708091 0.982093 0.53003 0.853035 0.687889 0.621508 0.886268 0.99639 0.769068 0.976249 0.942098 0.797744 0.95618 0.769761 0.54766 0.808601 0.768919 0.510475 0.796282 0.700578 0.95055 0.850628 0.59055 0....

output:

1.0000000

result:

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

Test #7:

score: 0
Accepted
time: 105ms
memory: 392448kb

input:

5000 400
0.949731 0.781106 0.989654 0.915645 0.820348 0.986255 0.556562 0.980361 0.585268 0.619063 0.638805 0.626075 0.712861 0.830454 0.752119 0.586471 0.790363 0.766842 0.728335 0.692244 0.512937 0.783807 0.770433 0.873134 0.700165 0.987424 0.825446 0.565547 0.583478 0.822277 0.670801 0.767487 0.7...

output:

1.0000000

result:

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

Test #8:

score: 0
Accepted
time: 102ms
memory: 392392kb

input:

5000 2210
0.71203 0.679108 0.907887 0.712217 0.893169 0.626399 0.906301 0.959817 0.750885 0.733514 0.798381 0.512897 0.500635 0.886224 0.796957 0.951011 0.733914 0.643075 0.681363 0.910476 0.97669 0.831855 0.579655 0.662137 0.786903 0.847733 0.984589 0.766957 0.535981 0.746778 0.795429 0.830155 0.94...

output:

0.9999986

result:

ok found '0.9999986', expected '0.9999986', error '0.0000000'

Test #9:

score: 0
Accepted
time: 102ms
memory: 392420kb

input:

5000 2435
0.85976 0.825175 0.988123 0.99143 0.946364 0.80865 0.946633 0.500816 0.791339 0.801104 0.595224 0.672078 0.595843 0.562347 0.6636 0.883299 0.717638 0.798594 0.843852 0.516739 0.75418 0.542577 0.708065 0.551775 0.576655 0.778256 0.999522 0.813346 0.690432 0.846349 0.711335 0.899078 0.82188 ...

output:

0.8823587

result:

ok found '0.8823587', expected '0.8823587', error '0.0000000'

Test #10:

score: 0
Accepted
time: 124ms
memory: 392428kb

input:

5000 2500
0.905245 0.789837 0.893132 0.880538 0.959228 0.767463 0.635301 0.788896 0.960618 0.588802 0.555198 0.539172 0.574133 0.898318 0.860345 0.520061 0.787785 0.679539 0.756813 0.617915 0.954852 0.693077 0.542528 0.514414 0.764342 0.836346 0.815288 0.786298 0.83269 0.843336 0.947585 0.897566 0.7...

output:

0.4540678

result:

ok found '0.4540678', expected '0.4540678', error '0.0000000'

Test #11:

score: 0
Accepted
time: 108ms
memory: 392448kb

input:

5000 2511
0.844207 0.714516 0.836117 0.737791 0.630006 0.845518 0.922792 0.545091 0.897151 0.994806 0.641675 0.820565 0.631293 0.524277 0.772035 0.613939 0.552815 0.682716 0.755224 0.92624 0.827741 0.83099 0.625213 0.609891 0.996279 0.991838 0.698857 0.870544 0.530011 0.834654 0.639099 0.855393 0.56...

output:

0.3589672

result:

ok found '0.3589672', expected '0.3589672', error '0.0000000'

Test #12:

score: 0
Accepted
time: 107ms
memory: 392420kb

input:

5000 2675
0.59012 0.755299 0.790643 0.925329 0.725113 0.547689 0.941098 0.656052 0.575288 0.756949 0.716317 0.658672 0.850807 0.500306 0.776437 0.573604 0.927024 0.505189 0.668677 0.688409 0.771328 0.564915 0.710954 0.817811 0.779639 0.640181 0.563585 0.790086 0.776722 0.501666 0.834008 0.672922 0.6...

output:

0.0004430

result:

ok found '0.0004430', expected '0.0004430', error '0.0000000'

Test #13:

score: 0
Accepted
time: 140ms
memory: 392368kb

input:

5000 4191
0.854051 0.667591 0.580349 0.742787 0.538388 0.92076 0.505213 0.751024 0.527905 0.719297 0.890786 0.768011 0.612651 0.511268 0.921473 0.525477 0.935572 0.771655 0.983739 0.976279 0.966472 0.556883 0.957248 0.913558 0.58931 0.575164 0.59759 0.676977 0.673129 0.525216 0.847845 0.746457 0.883...

output:

0.0000000

result:

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

Test #14:

score: 0
Accepted
time: 103ms
memory: 392360kb

input:

5000 5000
0.723988 0.943979 0.822556 0.787549 0.997458 0.981213 0.838612 0.584808 0.826804 0.876347 0.869831 0.777959 0.806646 0.935551 0.682757 0.529446 0.550732 0.614141 0.617399 0.708785 0.894561 0.583515 0.723974 0.697766 0.934301 0.645148 0.697407 0.61308 0.643698 0.677768 0.83191 0.934103 0.77...

output:

0.0000000

result:

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

Test #15:

score: 0
Accepted
time: 76ms
memory: 392444kb

input:

5000 5000
0.999992 0.999998 0.999997 0.999992 0.99999 0.999996 0.999991 0.99999 0.999996 0.999992 0.999999 0.999998 0.99999 0.999991 0.999997 0.999991 0.999992 0.999991 0.999991 0.999996 0.99999 0.999998 0.999998 0.999995 0.999992 1.0 0.999996 0.999994 0.999999 0.999994 0.999993 0.999999 0.999991 0....

output:

0.9750787

result:

ok found '0.9750787', expected '0.9750787', error '0.0000000'

Test #16:

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

input:

20 10
0.500005 0.50001 0.500004 0.5 0.500001 0.500001 0.500003 0.500004 0.500005 0.500008 0.500008 0.500002 0.500004 0.500009 0.500003 0.500004 0.500003 0.500009 0.500008 0.500006

output:

0.0206969

result:

ok found '0.0206969', expected '0.0206969', error '0.0000000'

Test #17:

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

input:

20 16
1.0 1.0 1.0 1.0 0.5 1.0 0.5 1.0 1.0 1.0 1.0 1.0 0.5 1.0 0.5 0.5 0.5 0.5 0.5 1.0

output:

0.1445312

result:

ok found '0.1445312', expected '0.1445312', error '0.0000001'

Test #18:

score: 0
Accepted
time: 79ms
memory: 392400kb

input:

5000 2000
1.0 0.5 1.0 1.0 1.0 1.0 1.0 0.5 1.0 1.0 0.5 1.0 0.5 1.0 1.0 0.5 1.0 0.5 1.0 0.5 0.5 1.0 0.5 0.5 1.0 1.0 0.5 0.5 1.0 0.5 0.5 0.5 0.5 0.5 1.0 0.5 0.5 1.0 0.5 1.0 1.0 1.0 0.5 1.0 0.5 1.0 0.5 0.5 1.0 1.0 1.0 1.0 1.0 1.0 0.5 1.0 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 1.0 1.0 0.5 1.0 1.0 0.5 1.0 1....

output:

1.0000000

result:

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

Test #19:

score: 0
Accepted
time: 75ms
memory: 392444kb

input:

5000 2600
1.0 1.0 0.5 0.5 0.5 1.0 0.5 0.5 0.5 0.5 1.0 0.5 0.5 1.0 1.0 1.0 0.5 0.5 1.0 1.0 0.5 0.5 0.5 0.5 0.5 1.0 1.0 0.5 0.5 1.0 0.5 0.5 1.0 0.5 0.5 0.5 0.5 1.0 0.5 1.0 0.5 1.0 1.0 1.0 1.0 0.5 1.0 0.5 1.0 1.0 1.0 0.5 1.0 1.0 0.5 0.5 0.5 1.0 0.5 1.0 1.0 0.5 0.5 0.5 0.5 0.5 1.0 1.0 1.0 0.5 0.5 0.5 1....

output:

0.1132373

result:

ok found '0.1132373', expected '0.1132373', error '0.0000000'

Test #20:

score: 0
Accepted
time: 151ms
memory: 392412kb

input:

5000 3000
0.7 0.6 0.6 0.6 0.6 0.7 0.7 0.7 0.6 0.7 0.7 0.6 0.6 0.6 0.6 0.6 0.6 0.7 0.7 0.7 0.7 0.7 0.6 0.7 0.7 0.7 0.7 0.7 0.6 0.7 0.6 0.6 0.7 0.6 0.6 0.7 0.7 0.6 0.7 0.7 0.6 0.6 0.7 0.6 0.7 0.6 0.6 0.7 0.6 0.6 0.6 0.6 0.7 0.7 0.6 0.6 0.6 0.7 0.7 0.6 0.7 0.7 0.7 0.7 0.6 0.7 0.7 0.6 0.7 0.6 0.7 0.7 0....

output:

0.0000000

result:

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

Test #21:

score: 0
Accepted
time: 88ms
memory: 392368kb

input:

5000 5000
0.9999 0.9999 0.9999 0.99999 0.99999 0.9999 0.99999 0.99999 0.99999 0.99999 0.9999 0.99999 0.9999 0.99999 0.9999 0.99999 0.9999 0.99999 0.99999 0.9999 0.99999 0.99999 0.99999 0.99999 0.9999 0.9999 0.9999 0.9999 0.99999 0.9999 0.9999 0.99999 0.9999 0.99999 0.99999 0.9999 0.99999 0.9999 0.99...

output:

0.7647760

result:

ok found '0.7647760', expected '0.7647760', error '0.0000000'

Test #22:

score: 0
Accepted
time: 112ms
memory: 392384kb

input:

5000 1
0.50001 0.50001 0.50001 0.50001 0.50001 0.50001 0.50001 0.50001 0.5 0.5 0.50001 0.50001 0.50001 0.5 0.50001 0.5 0.50001 0.50001 0.50001 0.5 0.5 0.5 0.50001 0.5 0.50001 0.5 0.5 0.5 0.50001 0.5 0.5 0.50001 0.50001 0.50001 0.5 0.5 0.5 0.50001 0.50001 0.50001 0.50001 0.50001 0.50001 0.5 0.5 0.500...

output:

0.5003999

result:

ok found '0.5003999', expected '0.5003999', error '0.0000000'

Test #23:

score: 0
Accepted
time: 76ms
memory: 392388kb

input:

5000 2550
0.99999 0.99999 0.99999 0.99999 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.99999 0.99999 0.5 0.99999 0.5 0.99999 0.5 0.5 0.99999 0.99999 0.5 0.99999 0.99999 0.5 0.99999 0.5 0.5 0.5 0.99999 0.99999 0.99999 0.99999 0.5 0.99999 0.5 0.5 0.99999 0.99999 0.5 0.99999 0.99999 0.5 0.5 0.99999 0.5 0.5 0.99999 0....

output:

0.1889263

result:

ok found '0.1889263', expected '0.1889263', error '0.0000000'

Test #24:

score: 0
Accepted
time: 152ms
memory: 392444kb

input:

5000 1000
0.573979 0.66648 0.837479 0.646164 0.82281 0.503116 0.750598 0.506659 0.590989 0.723873 0.814274 0.533182 0.55926 0.500155 0.643449 0.895303 0.953762 0.545179 0.700636 0.614141 0.50281 0.601696 0.89439 0.784236 0.732711 0.612275 0.713909 0.505734 0.781685 0.557303 0.634015 0.809354 0.52173...

output:

0.9999770

result:

ok found '0.9999770', expected '0.9999770', error '0.0000000'

Test #25:

score: 0
Accepted
time: 160ms
memory: 392380kb

input:

5000 1250
0.558686 0.504831 0.794092 0.55769 0.613812 0.51749 0.675135 0.90028 0.643215 0.747141 0.680045 0.763593 0.790229 0.634649 0.54581 0.521091 0.882598 0.939849 0.588177 0.847337 0.608842 0.632905 0.771339 0.659504 0.525063 0.84975 0.503895 0.528513 0.622738 0.534078 0.508869 0.577018 0.53623...

output:

0.5192497

result:

ok found '0.5192497', expected '0.5192497', error '0.0000000'

Test #26:

score: 0
Accepted
time: 146ms
memory: 392384kb

input:

5000 1500
0.566069 0.654367 0.574283 0.530919 0.577292 0.622283 0.569832 0.780864 0.622053 0.522289 0.846109 0.617616 0.598611 0.550527 0.523834 0.55392 0.780419 0.511342 0.548441 0.640521 0.918236 0.856115 0.521631 0.772784 0.582256 0.66865 0.533183 0.797523 0.902415 0.794695 0.512854 0.501768 0.52...

output:

0.0002087

result:

ok found '0.0002087', expected '0.0002087', error '0.0000000'

Test #27:

score: 0
Accepted
time: 96ms
memory: 392388kb

input:

5000 1
0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0...

output:

0.9000000

result:

ok found '0.9000000', expected '0.9000000', error '0.0000000'

Test #28:

score: 0
Accepted
time: 107ms
memory: 392400kb

input:

5000 2
0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0...

output:

0.8100000

result:

ok found '0.8100000', expected '0.8100000', error '0.0000000'

Test #29:

score: 0
Accepted
time: 99ms
memory: 392424kb

input:

5000 3
0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0...

output:

0.4977430

result:

ok found '0.4977430', expected '0.4977430', error '0.0000000'