QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#103981#4994. Graduation GuaranteeJorgeSCAC ✓164ms199544kbC++143.1kb2023-05-08 06:39:002023-05-08 06:39:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-08 06:39:02]
  • 评测
  • 测评结果:AC
  • 用时:164ms
  • 内存:199544kb
  • [2023-05-08 06:39:00]
  • 提交

answer

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

// --------------------------- Defines -------------------------------------  //
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<
    typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type
> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

#ifdef FILE_STREAM
streambuf *cin_backup = cin.rdbuf(), *cout_backup = cout.rdbuf();
ifstream f_in("name.in");
ofstream f_out("name.out");
#endif // FILE_STREAM

#ifdef DEBUG
    #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
    #define dbg(...)
#endif

#define ll long long
#define fill_array(x, y) memset(x, y, sizeof(x))
#define out_range_map(x,y) ((x) < 0 || (y) < 0 || (x) == N || (y) == M)
#define sza(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define fori(i, N) for(int i = 0; i < N; i++)
#define left(x) (x << 1 | 1)
#define right(x) (left(x) + 1)
#define half (l + r) / 2
// --------------------------- /Defines/ ------------------------------------ //

// --------------------------- Constants ----------------------------------- //
const ll LN = (ll)(5e3 + 5), 
         LM = (ll)(1e2 + 5), 
         INF = (ll)(1e15), 
         MOD = (ll)(1e9);
ll N, M, K, T, Q;
// -------------------------- /Constants/ ---------------------------------- //
vector < double > prob;
double memo[LN][LN];

double dp(int i, int k)
{
    if(memo[i][k] != -1)
        return memo[i][k];
    if(k > i + 1)
        return memo[i][k] = 0;
    if (k == 0)
        return memo[i][k] = (i ? dp(i-1,0)*(1-prob[i]) : (1-prob[0]));
    if (i == 0)
        return memo[0][1] = prob[0];
    
    return memo[i][k] = dp(i - 1, k)*(1-prob[i]) + dp(i - 1, k - 1) * prob[i];
}

// ------------------------- Your code ---------------------------------- //
void Solve() {
	
    cin >> N >> K;

    prob.resize(N);

    for (int i = 0; i < N; i++)
        cin >> prob[i];

    sort(all(prob), greater<double>());

    for (int i = 0; i <= N; i++)
        for (int j = 0; j <= N; j++)
            memo[i][j] = -1;

    double ans = -1.0, tans;
    for (int i = K-1; i < N; i++)
    {
        tans = 0.0;
        for (int k = (K + i + 2)/2; k <= i + 1; k++)
            tans += dp(i,k);
        ans = max(ans, tans);
    }

    cout << ans << '\n';
    
}
// --------------------------------------------------------------------- //

int main() {
    #ifdef DEBUG
        freopen("input.txt","w",stdin);
        freopen("output.txt","w",stdout);
    #else
        //ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int Tc = 1;
    // cin >> Tc;

    fori(i, Tc)
        Solve();

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3588kb

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: 3740kb

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: 3688kb

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: 5856kb

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

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: 116ms
memory: 199308kb

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: 144ms
memory: 199320kb

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: 151ms
memory: 199544kb

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: 146ms
memory: 199540kb

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: 150ms
memory: 199540kb

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: 149ms
memory: 199384kb

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: 137ms
memory: 199416kb

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

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: 20ms
memory: 199428kb

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: 31ms
memory: 199536kb

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: 3636kb

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

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: 157ms
memory: 199316kb

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: 149ms
memory: 199544kb

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: 133ms
memory: 199436kb

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: 25ms
memory: 199492kb

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: 126ms
memory: 199460kb

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: 164ms
memory: 199384kb

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: 136ms
memory: 199500kb

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: 146ms
memory: 199500kb

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: 152ms
memory: 199384kb

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: 133ms
memory: 199288kb

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: 130ms
memory: 199340kb

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: 133ms
memory: 199348kb

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'