QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#134695 | #2440. Valentine's Day | ckiseki# | AC ✓ | 117ms | 3948kb | C++14 | 1.6kb | 2023-08-04 15:35:16 | 2023-08-04 15:35:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int cnt = sizeof...(T);
(..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
cerr << "\e[1;32m[ " << s << " ] = [ ";
for (int f = 0; L != R; L++)
cerr << (f++ ? ", " : "") << *L;
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
using llf = long double;
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<llf> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
}
sort(p.begin(), p.end());
if (p.back() == 1) {
cout << 1 << '\n';
continue;
}
llf ans = p.back();
llf prod = 1, sum = 0;
for (int i = 0, r = 0; i < n; i++) {
while (r < n && prod * sum <= (prod * (1 - p[r]) * (sum + p[r] / (1 - p[r])))) {
prod *= (1 - p[r]);
sum += p[r] / (1 - p[r]);
++r;
ans = max(ans, prod * sum);
}
prod /= 1 - p[i];
sum -= p[i] / (1 - p[i]);
ans = max(ans, prod * sum);
}
cout << fixed << setprecision(20) << ans << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 117ms
memory: 3948kb
input:
100 10 0.020874 0.180969 0.015588 0.043033 0.181293 0.033025 0.163341 0.104341 0.065442 0.129546 10 0.019357 0.210598 0.045487 0.051145 0.014579 0.135566 0.004401 0.008004 0.106695 0.056974 10 0.062679 0.216144 0.010137 0.031823 0.233062 0.042464 0.099544 0.140483 0.201337 0.045349 100 0.116404 0.19...
output:
0.39819007148890732530 0.37368388645907640543 0.41088536275849987464 0.42137404437828100437 0.41987297101569753051 0.42106225701885684700 0.42079685802045167309 0.41989089757572841061 0.41986039320215500813 0.00009999010048508432 0.00000000000000000000 0.00334100000000000000 0.00333600000000000000 0...
result:
ok 100 numbers