QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #297576 | #4994. Graduation Guarantee | PhantomThreshold# | AC ✓ | 160ms | 4212kb | C++20 | 1.1kb | 2024-01-04 19:29:49 | 2024-01-04 19:29:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long double db;
const int maxn=5000;
int n,K;
db a[maxn+50];
int main(){
ios_base::sync_with_stdio(false);
cin >> n >> K;
for (int i=1;i<=n;i++) cin >> a[i];
sort(a+1,a+n+1,greater<db>());
vector<db> poly(1,1.0);
db ans=0;
for (int i=1;i<=n;i++){
vector<db> nxt(poly.size()+2);
for (int j=0;j<(int)poly.size();j++){
nxt[j+2]+=poly[j]*a[i];
nxt[j]+=poly[j]*(1.0-a[i]);
}
db sum=0;
int st=(K+n)-(n-i);
st=max(st,0);
/*
cerr << "i : " << i << endl;
cerr << "st: " << st << endl;
for (auto e:poly) cerr << e << " ";cerr << endl;
for (auto e:nxt) cerr << e << " ";cerr << endl;
*/
for (int j=st;j<(int)nxt.size();j++) sum+=nxt[j];
ans=max(ans,sum);
swap(poly,nxt);
}
cout << fixed << setprecision(12) << ans << "\n";
return 0;
}
/*
4 1
0.9 0.5 0.9 0.9
i : 1
st: 0
1
0.1 0 0.9
i : 2
st: 0
0.1 0 0.9
0.01 0 0.18 0 0.81
i : 3
st: 1
0.01 0 0.18 0 0.81
0.001 0 0.027 0 0.243 0 0.729
i : 4
st: 2
0.001 0 0.027 0 0.243 0 0.729
0.0005 0 0.014 0 0.135 0 0.486 0 0.3645
1.000000000000
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3740kb
input:
3 3 0.5 0.5 0.5
output:
0.125000000000
result:
ok found '0.1250000', expected '0.1250000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
4 1 0.9 0.5 0.9 0.9
output:
0.972000000000
result:
ok found '0.9720000', expected '0.9720000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3736kb
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.726170426941
result:
ok found '0.7261704', expected '0.7261704', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3736kb
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.537372370590
result:
ok found '0.5373724', expected '0.5373724', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
1 1 0.744983
output:
0.744983000000
result:
ok found '0.7449830', expected '0.7449830', error '0.0000000'
Test #6:
score: 0
Accepted
time: 125ms
memory: 4000kb
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.000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 144ms
memory: 4144kb
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.000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 134ms
memory: 4212kb
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.999998613546
result:
ok found '0.9999986', expected '0.9999986', error '0.0000000'
Test #9:
score: 0
Accepted
time: 137ms
memory: 4036kb
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.882358740908
result:
ok found '0.8823587', expected '0.8823587', error '0.0000000'
Test #10:
score: 0
Accepted
time: 134ms
memory: 4108kb
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.454067801731
result:
ok found '0.4540678', expected '0.4540678', error '0.0000000'
Test #11:
score: 0
Accepted
time: 141ms
memory: 4104kb
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.358967211448
result:
ok found '0.3589672', expected '0.3589672', error '0.0000000'
Test #12:
score: 0
Accepted
time: 137ms
memory: 4000kb
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.000443026685
result:
ok found '0.0004430', expected '0.0004430', error '0.0000000'
Test #13:
score: 0
Accepted
time: 147ms
memory: 3964kb
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.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #14:
score: 0
Accepted
time: 151ms
memory: 4104kb
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.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #15:
score: 0
Accepted
time: 160ms
memory: 4000kb
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.975078708044
result:
ok found '0.9750787', expected '0.9750787', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3868kb
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.020696884087
result:
ok found '0.0206969', expected '0.0206969', error '0.0000000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 4008kb
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.144531250000
result:
ok found '0.1445312', expected '0.1445312', error '0.0000000'
Test #18:
score: 0
Accepted
time: 139ms
memory: 3964kb
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.000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #19:
score: 0
Accepted
time: 144ms
memory: 4088kb
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.113237345795
result:
ok found '0.1132373', expected '0.1132373', error '0.0000000'
Test #20:
score: 0
Accepted
time: 133ms
memory: 4084kb
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.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #21:
score: 0
Accepted
time: 136ms
memory: 4112kb
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.764776037383
result:
ok found '0.7647760', expected '0.7647760', error '0.0000000'
Test #22:
score: 0
Accepted
time: 153ms
memory: 4008kb
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.500399858732
result:
ok found '0.5003999', expected '0.5003999', error '0.0000000'
Test #23:
score: 0
Accepted
time: 143ms
memory: 3992kb
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.188926259618
result:
ok found '0.1889263', expected '0.1889263', error '0.0000000'
Test #24:
score: 0
Accepted
time: 154ms
memory: 4000kb
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.999976958883
result:
ok found '0.9999770', expected '0.9999770', error '0.0000000'
Test #25:
score: 0
Accepted
time: 141ms
memory: 3932kb
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.519249666388
result:
ok found '0.5192497', expected '0.5192497', error '0.0000000'
Test #26:
score: 0
Accepted
time: 152ms
memory: 4084kb
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.000208704270
result:
ok found '0.0002087', expected '0.0002087', error '0.0000000'
Test #27:
score: 0
Accepted
time: 157ms
memory: 4036kb
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.900000000000
result:
ok found '0.9000000', expected '0.9000000', error '0.0000000'
Test #28:
score: 0
Accepted
time: 146ms
memory: 4144kb
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.810000000000
result:
ok found '0.8100000', expected '0.8100000', error '0.0000000'
Test #29:
score: 0
Accepted
time: 149ms
memory: 3992kb
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.497742993365
result:
ok found '0.4977430', expected '0.4977430', error '0.0000000'