QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#756196 | #8037. Gambler's Ruin | Symmetree | WA | 1ms | 10036kb | C++17 | 1.3kb | 2024-11-16 19:20:13 | 2024-11-16 19:20:14 |
Judging History
answer
#include<bits/stdc++.h>
const int N = 1e6+5;
using i64 = long long;
std::pair<double, int> p[N];
i64 pre[N], suf[N];
double f[22][N];
int n, mxp[N], t[N];
#define fi first
#define se second
signed main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%lf%d", &p[i].fi, &p[i].se);
std::sort(p + 1, p + n + 1);
for(int i = 1; i <= n; ++i) {
pre[i] = pre[i - 1] + p[i].se;
f[0][i] = 1.0 * pre[i] - 1.0 * pre[i] / (1 - p[i].fi);
}
for(int i = 2; i <= n; ++i) t[i] = t[i >> 1] + 1;
for(int i = n; i; --i) suf[i] = suf[i + 1] + p[i].se;
for(int k = 1; k < 21; ++k)
for(int i = 1; i + (1 << k) - 1 <= n; ++i)
f[k][i] = std::max(f[k - 1][i], f[k - 1][i + (1 << (k - 1))]);
double ans = -1e18;
for(int i = 1; i <= n; ++i) {
int pos, l = 1, r = i - 1;
double bd = 1.0 * suf[i] / p[i].fi;
ans = std::max(ans, 1.0 * suf[i] - bd);
if(i == 1) continue;
while(l < r) {
int mid = (l + r) >> 1;
if(1.0 * pre[mid] / (1.0 - p[mid].fi) >= bd) r = mid;
else l = mid + 1;
}
if(1.0 * pre[r] / (1.0 - p[r].fi) >= bd) {
int k = t[i - r];
ans = std::max(ans, 1.0 * suf[i] + std::max(f[k][r], f[k][i - (1 << k)]));
if(r > 1) ans = std::max(ans, 1.0 * suf[i] + 1.0 * pre[r - 1] - bd);
}
else
ans = std::max(ans, 1.0 * suf[i] + 1.0 * pre[i - 1] - bd);
}
printf("%.10lf\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 10012kb
input:
2 1 15 0 10
output:
10.0000000000
result:
ok found '10.0000000', expected '10.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 10036kb
input:
3 0.4 100 0.5 100 0.6 100
output:
33.3333333333
result:
ok found '33.3333333', expected '33.3333333', error '0.0000000'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 7932kb
input:
1 0 1
output:
-1000000000000000000.0000000000
result:
wrong answer 1st numbers differ - expected: '0.0000000', found: '-1000000000000000000.0000000', error = '1000000000000000000.0000000'