QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#773041#8037. Gambler's RuinAndevikingWA 1ms3964kbC++201.9kb2024-11-23 00:04:152024-11-23 00:04:15

Judging History

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

  • [2024-11-23 00:04:15]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3964kb
  • [2024-11-23 00:04:15]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

vector<long double> p;
vector<ll> c;
int n;
const long double EPS = 1e-10L;
long double f(long double x, long double y)
{
    ll sx = 0, sy = 0;
    for (int i = 1; i <= n; ++i)
        if (p[i] * x >= 1)
            sx += c[i];
        else if ((1 - p[i]) * y >= 1)
            sy += c[i];
    // cout << sx << ' ' << sy << ' ' << x << ' ' << y << ' ' << sx + sy - max(sx * x, sy * y) << '\n';
    return sx + sy - max(sx * x, sy * y);
}
long double get(long double x)
{
    long double l = 0, r = 2000000;
    long double lans = f(x, l), rans = f(x, r);
    long double ans = max(lans, rans);
    for (int _ = 0; _ < 100; ++_) {
        long double lmid = l + (r - l) / 3;
        long double rmid = r - (r - l) / 3;

        lans = f(x, lmid), rans = f(x, rmid);
        ans = max(lans, rans);
        if (lans - rans >= EPS)
            r = rmid;
        else
            l = lmid;
    }
    // cout << x << ' ' << l << ' ' << ans << '\n';
    return ans;
}
void solve()
{
    cin >> n;
    p.resize(n + 5);
    c.resize(n + 5);
    for (int i = 1; i <= n; ++i)
        cin >> p[i] >> c[i];

    long double l = 0, r = 2000000;
    long double lans = get(l), rans = get(r);
    long double ans = max(lans, rans);
    for (int _ = 0; _ < 100; ++_) {
        long double lmid = l + (r - l) / 3;
        long double rmid = r - (r - l) / 3;

        lans = get(lmid), rans = get(rmid);
        ans = max(lans, rans);
        if (lans - rans >= EPS)
            r = rmid;
        else
            l = lmid;
    }
    // cout << f(1 / .6L, 1.9) << '\n';
    // cout << get(1 / .6L) << '\n';
    cout << fixed << setprecision(10) << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    while (T--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3848kb

input:

2
1 15
0 10

output:

9.9999999998

result:

ok found '10.0000000', expected '10.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3924kb

input:

3
0.4 100
0.5 100
0.6 100

output:

33.3333333332

result:

ok found '33.3333333', expected '33.3333333', error '0.0000000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3896kb

input:

1
0 1

output:

-0.0000000002

result:

ok found '-0.0000000', expected '0.0000000', error '0.0000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3964kb

input:

2
1 0
1 100

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3852kb

input:

1
0.5 100

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3876kb

input:

3
0.4 100
0.6 100
0.6 100

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3964kb

input:

3
0.2 100
0.2 100
0.8 100

output:

50.0000000000

result:

ok found '50.0000000', expected '50.0000000', error '0.0000000'

Test #8:

score: -100
Wrong Answer
time: 1ms
memory: 3856kb

input:

2
0.999999 1000000
0.999998 2

output:

0.9999966051

result:

wrong answer 1st numbers differ - expected: '0.9999990', found: '0.9999966', error = '0.0000024'