QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#103981 | #4994. Graduation Guarantee | JorgeSC | AC ✓ | 164ms | 199544kb | C++14 | 3.1kb | 2023-05-08 06:39:00 | 2023-05-08 06:39:02 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'