QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#521264#4994. Graduation GuaranteergnerdplayerAC ✓125ms4256kbC++20988b2024-08-16 02:04:412024-08-16 02:04:41

Judging History

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

  • [2024-08-16 02:04:41]
  • 评测
  • 测评结果:AC
  • 用时:125ms
  • 内存:4256kb
  • [2024-08-16 02:04:41]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    auto solve = [&]() {
        int n, k;
        cin >> n >> k;

        vector<double> p(n);
        for (int i = 0; i < n; i++) {
            cin >> p[i];
        }

        sort(p.rbegin(), p.rend());

        double ans = 0;
        vector<double> dp(2 * n + 1), ndp(dp);
        dp[n] = 1;

        for (int i = 0; i < n; i++) {
            fill(ndp.begin(), ndp.end(), 0);
            for (int x = 0; x <= 2 * n; x++) {
                if (dp[x] != 0) {
                    ndp[x - 1] += dp[x] * (1 - p[i]);
                    ndp[x + 1] += dp[x] * p[i];
                }
            }
            ans = max(ans, accumulate(ndp.begin() + n + k, ndp.end(), 0.0));
            swap(dp, ndp);
        }

        cout << fixed << setprecision(20) << ans << '\n';
    };
    
    solve();
    
    return 0;
}

詳細信息

Test #1:

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

input:

3 3
0.5 0.5 0.5

output:

0.12500000000000000000

result:

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

Test #2:

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

input:

4 1
0.9 0.5 0.9 0.9

output:

0.97200000000000008615

result:

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

Test #3:

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

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

result:

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

Test #4:

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

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

result:

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

Test #5:

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

input:

1 1
0.744983

output:

0.74498299999999995080

result:

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

Test #6:

score: 0
Accepted
time: 87ms
memory: 4068kb

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

result:

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

Test #7:

score: 0
Accepted
time: 84ms
memory: 4168kb

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

result:

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

Test #8:

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

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

result:

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

Test #9:

score: 0
Accepted
time: 73ms
memory: 4240kb

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

result:

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

Test #10:

score: 0
Accepted
time: 73ms
memory: 3944kb

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

result:

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

Test #11:

score: 0
Accepted
time: 70ms
memory: 4232kb

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

result:

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

Test #12:

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

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

result:

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

Test #13:

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

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

result:

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

Test #14:

score: 0
Accepted
time: 58ms
memory: 3960kb

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

result:

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

Test #15:

score: 0
Accepted
time: 37ms
memory: 4072kb

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

result:

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

Test #16:

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

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

result:

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

Test #17:

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

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

result:

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

Test #18:

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

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

result:

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

Test #19:

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

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

result:

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

Test #20:

score: 0
Accepted
time: 111ms
memory: 4100kb

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

result:

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

Test #21:

score: 0
Accepted
time: 34ms
memory: 4100kb

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

result:

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

Test #22:

score: 0
Accepted
time: 95ms
memory: 3956kb

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

result:

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

Test #23:

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

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

result:

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

Test #24:

score: 0
Accepted
time: 125ms
memory: 3948kb

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

result:

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

Test #25:

score: 0
Accepted
time: 123ms
memory: 4004kb

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

result:

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

Test #26:

score: 0
Accepted
time: 125ms
memory: 4140kb

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

result:

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

Test #27:

score: 0
Accepted
time: 77ms
memory: 3952kb

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

result:

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

Test #28:

score: 0
Accepted
time: 80ms
memory: 4128kb

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

result:

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

Test #29:

score: 0
Accepted
time: 81ms
memory: 4068kb

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

result:

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