QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#628979 | #8037. Gambler's Ruin | lonelywolf | WA | 0ms | 4048kb | C++20 | 1.5kb | 2024-10-10 23:44:52 | 2024-10-10 23:44:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
using db = double;
constexpr db eps = 1e-9;
int sgn(db x) {
if (x > eps) {
return 1;
} else if (x < -eps) {
return -1;
}
return 0;
}
int cmp(db x, db y) {
return sgn(x - y);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<db> p_(n + 1), c_(n + 1);
for (int i = 1; i <= n; i++) {
cin >> p_[i] >> c_[i];
}
vector<int> ord(n + 1);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin() + 1, ord.end(), [&](int i, int j) {
return p_[i] > p_[j];
});
vector<db> p(1, -1);
vector<int> c(1);
for (int i = 1; i <= n; i++) {
if (cmp(p.back(), p_[ord[i]]) == 0) {
c[c.size() - 1] += c_[ord[i]];
} else {
p.push_back(p_[ord[i]]);
c.push_back(c_[ord[i]]);
}
}
vector<int> suf(n + 2);
for (int i = n; i >= 1; i--) {
suf[i] = suf[i + 1] + c[i];
}
n = p.size() - 1;
int sx = 0;
db ans = -1e18;
for (int i = 1; i <= n; i++) {
db x = 1.0 / p[i];
sx += c[i];
auto calc = [&](int m) {
db y = 1.0 / (1 - p[m]);
db sy = suf[m];
return 1.0 * sx + 1.0 * sy - max(x * sx, y * sy);
};
int l = i, r = n + 1;
while (r - l > 5) {
int lm = (2 * l + r) / 3, rm = (l + 2 * r) / 3;
if (calc(lm) < calc(rm)) {
l = lm;
} else {
r = rm;
}
}
for (int t = l; t <= r; t++) {
ans = max(ans, calc(t));
}
}
cout << fixed << setprecision(10) << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3820kb
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: 0ms
memory: 3900kb
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: 4048kb
input:
1 0 1
output:
-1000000000000000000.0000000000
result:
wrong answer 1st numbers differ - expected: '0.0000000', found: '-1000000000000000000.0000000', error = '1000000000000000000.0000000'