QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#153217 | #4994. Graduation Guarantee | value0 | AC ✓ | 88ms | 786372kb | C++20 | 1.2kb | 2023-08-29 17:49:30 | 2023-08-29 17:49:31 |
Judging History
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'