QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#111254#4994. Graduation GuaranteePetroTarnavskyi#AC ✓107ms394236kbC++171021b2023-06-06 14:56:072023-06-06 14:56:10

Judging History

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

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

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

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	double ans = 0;
	vector<double> p(n);
	FOR (i, 0, n) cin >> p[i];
	sort(ALL(p), greater());
	vector<vector<double>> dp(n + 1, vector<double>(2 * n + 1, 0));
	dp[0][n] = 1;
	double cur = 0;
	FOR (i, 0, n)
	{
		cur = 0;
		FOR (j, -i, i + 1)
		{
			if (j >= k) cur += dp[i][n + j];
			dp[i + 1][n + j + 1] += dp[i][n + j] * p[i];
			dp[i + 1][n + j - 1] += dp[i][n + j] * (1 - p[i]);
		}
		ans = max(ans, cur);
	}
	cur = 0; 
	FOR (i, k, n + 1) cur += dp[n][n + i];
	ans = max(ans, cur);
	cout << ans << '\n';
	
	
	return 0;
}

詳細信息

Test #1:

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

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: 2ms
memory: 3576kb

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: 2ms
memory: 3612kb

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: 2ms
memory: 3784kb

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: 0ms
memory: 3604kb

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: 97ms
memory: 394076kb

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: 98ms
memory: 394160kb

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: 105ms
memory: 394080kb

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: 77ms
memory: 394164kb

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: 82ms
memory: 394164kb

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: 96ms
memory: 394176kb

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: 97ms
memory: 394156kb

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: 89ms
memory: 394160kb

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: 99ms
memory: 394224kb

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: 93ms
memory: 394084kb

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: 2ms
memory: 3704kb

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: 0ms
memory: 3652kb

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: 89ms
memory: 394160kb

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: 86ms
memory: 394168kb

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: 81ms
memory: 394172kb

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: 104ms
memory: 394088kb

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: 80ms
memory: 394224kb

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: 68ms
memory: 394180kb

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: 82ms
memory: 394088kb

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: 100ms
memory: 394076kb

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: 91ms
memory: 394076kb

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: 107ms
memory: 394236kb

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: 80ms
memory: 394192kb

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: 89ms
memory: 394180kb

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'