QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#153217#4994. Graduation Guaranteevalue0AC ✓88ms786372kbC++201.2kb2023-08-29 17:49:302023-08-29 17:49:31

Judging History

This is the latest submission verdict.

  • [2023-08-29 17:49:31]
  • Judged
  • Verdict: AC
  • Time: 88ms
  • Memory: 786372kb
  • [2023-08-29 17:49:30]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n;
ll k;

int main()
{
	cin>>n>>k;
	//f[i][j]:Ñ¡ÔñµÄ´ðÇ°i¸öÌâÄ¿£¬×îÖյ÷ÖΪjµÄ¸ÅÂÊ 
	vector<vector<double>> f(2 * n + 10,vector<double>(2 * n + 10));
	ll bas = n + 1;
	vector<double> a(n + 1);
	for(int i = 1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a.begin()+1,a.end());
	reverse(a.begin()+1,a.end());
	//Ò»ÌⲻѡµÄÄÃ0·ÖµÄ¸ÅÂÊÊÇ1 
	f[0][bas] = 1;
	double ans = 0;
	//×ö¶Ô¸ÅÂÊ×î´óµÄkÌâÈ«²¿¶ÔµÄ¸ÅÂʾÍÊÇ×î´ó¼°¸ñ¸ÅÂÊ 
	// ps:×¢ÒâÕâÀï´ð´íÁËÒª¼õ·ÖµÄ 
	for(int i = 1;i <= n;i++)
	{
		ll l = bas - i;
		ll r = bas + i;
		//´ÓÈ«´íµ½È«¶Ô 
		for(int j = l;j <= r;j++)
		{
			f[i][j] = f[i-1][j-1] * a[i] + f[i-1][j+1] * (1.0 - a[i]);
//			cout<<f[i][j]<<endl;
//			cout<<i<<' '<<j<<endl;
		}
		double res = 0;
		for(int j = k + bas;j<=r;j++)
		{
			res += f[i][j];
		}
//		cout<<res<<endl;
		ans = max(ans,res);
	}
//	for(int i = 1;i<=n;i++)
//	{
//		for(int j = k;j<=i;j++)
//		{
//			ans += f[i][j];
//		}
//	}
	cout<<ans<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3664kb

input:

3 3
0.5 0.5 0.5

output:

0.125

result:

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

Test #2:

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

input:

4 1
0.9 0.5 0.9 0.9

output:

0.972

result:

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

Test #3:

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

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.72617

result:

ok found '0.7261700', expected '0.7261704', error '0.0000004'

Test #4:

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

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.537372

result:

ok found '0.5373720', expected '0.5373724', error '0.0000004'

Test #5:

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

input:

1 1
0.744983

output:

0.744983

result:

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

Test #6:

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

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

result:

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

Test #7:

score: 0
Accepted
time: 69ms
memory: 786340kb

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

result:

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

Test #8:

score: 0
Accepted
time: 47ms
memory: 786296kb

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.999999

result:

ok found '0.9999990', expected '0.9999986', error '0.0000004'

Test #9:

score: 0
Accepted
time: 48ms
memory: 786372kb

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.882359

result:

ok found '0.8823590', expected '0.8823587', error '0.0000003'

Test #10:

score: 0
Accepted
time: 60ms
memory: 786368kb

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.454068

result:

ok found '0.4540680', expected '0.4540678', error '0.0000002'

Test #11:

score: 0
Accepted
time: 72ms
memory: 786316kb

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.358967

result:

ok found '0.3589670', expected '0.3589672', error '0.0000002'

Test #12:

score: 0
Accepted
time: 44ms
memory: 786316kb

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.000443027

result:

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

Test #13:

score: 0
Accepted
time: 49ms
memory: 786296kb

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:

3.09872e-228

result:

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

Test #14:

score: 0
Accepted
time: 64ms
memory: 786372kb

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

result:

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

Test #15:

score: 0
Accepted
time: 49ms
memory: 786336kb

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.975079

result:

ok found '0.9750790', expected '0.9750787', error '0.0000003'

Test #16:

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

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: 1ms
memory: 3600kb

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.144531

result:

ok found '0.1445310', expected '0.1445312', error '0.0000003'

Test #18:

score: 0
Accepted
time: 69ms
memory: 786324kb

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

result:

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

Test #19:

score: 0
Accepted
time: 65ms
memory: 786340kb

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.113237

result:

ok found '0.1132370', expected '0.1132373', error '0.0000003'

Test #20:

score: 0
Accepted
time: 68ms
memory: 786324kb

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:

8.80391e-120

result:

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

Test #21:

score: 0
Accepted
time: 61ms
memory: 786296kb

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.764776

result:

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

Test #22:

score: 0
Accepted
time: 53ms
memory: 786364kb

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.5004

result:

ok found '0.5004000', expected '0.5003999', error '0.0000001'

Test #23:

score: 0
Accepted
time: 62ms
memory: 786308kb

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.188926

result:

ok found '0.1889260', expected '0.1889263', error '0.0000003'

Test #24:

score: 0
Accepted
time: 55ms
memory: 786372kb

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.999977

result:

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

Test #25:

score: 0
Accepted
time: 56ms
memory: 786320kb

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.51925

result:

ok found '0.5192500', expected '0.5192497', error '0.0000003'

Test #26:

score: 0
Accepted
time: 52ms
memory: 786320kb

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.000208704

result:

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

Test #27:

score: 0
Accepted
time: 60ms
memory: 786320kb

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.9

result:

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

Test #28:

score: 0
Accepted
time: 68ms
memory: 786336kb

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.81

result:

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

Test #29:

score: 0
Accepted
time: 53ms
memory: 786368kb

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.497743

result:

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