QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#842690#9966. High Jumpucup-team3474#WA 38ms6756kbC++233.5kb2025-01-04 14:07:192025-01-04 14:07:20

Judging History

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

  • [2025-01-04 14:07:20]
  • 评测
  • 测评结果:WA
  • 用时:38ms
  • 内存:6756kb
  • [2025-01-04 14:07:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std ;
#define vec point
typedef double db;
const db eps = 1e-6;
const db pi = acos(-1.0);
const db inf = 40000;
int sgn(db x) {
    if (x < -eps)
        return -1;
    else if (x > eps)
        return 1;
    else
        return 0;
}
int cmp(db x, db y) { return sgn(x - y); }
void print(int num, db x) { cout << fixed << setprecision(num) << x << '\n'; }
struct point {
    db x, y;
    point() {}
    point(db x2, db y2) { x = x2, y = y2; }
    void input() {
        int x2, y2;
        cin >> x2 >> y2;
        x = x2;
        y = y2;
    }
    point operator+(const point &s) const { return (point){x + s.x, y + s.y}; }
    point operator-(const point &s) const { return (point){x - s.x, y - s.y}; }
    point operator*(const db &k) const { return (point){x * k, y * k}; }
    point operator/(const db &k) const { return (point){x / k, y / k}; }
    db operator*(const point &a) const { return x * a.x + y * a.y; }
    db operator^(const point &a) const { return x * a.y - y * a.x; }
    bool operator<(point b) const { return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x; }
    bool equal(point p2) { return cmp(x, p2.x) == 0 && cmp(y, p2.y) == 0; }
    db get_angle() { return atan2(y, x); }
    int getP() const { return sgn(y) == 1 || (sgn(y) == 0 && sgn(x) == -1); }
    db sq(db x) { return x * x; }
    db dis(point p) { return sqrtl(sq(x - p.x) + sq(y - p.y)); }
    db len() { return sqrtl(sq(x) + sq(y)); }
    db len2() { return sq(x) + sq(y); }
    point unit() {
        db w = len();
        return (point){x / w, y / w};
    }
    vec rotate_left() { return vec(-y, x); }
    vec rotate_right() { return vec(y, -x); }
    point move(db r) {
        db l = len();
        if (sgn(l) == 0)
            return *this;
        else
            return point(x * r / l, y * r / l);
    }
    vec rotate(db ang) { return vec({x * cos(ang) - y * sin(ang), y * cos(ang) + x * sin(ang)}); }
};
db cross(vec s, vec t) { return s.x * t.y - s.y * t.x; }
db dot(vec s, vec t) { return s.x * t.x + s.y * t.y; }
void solve()
{
    int n ;
    cin >> n ;
    vector<db> p(n) ;
    for(int i = 0 ; i < n ; i ++)  cin >> p[i] ;
    // dp[i] = \max val[i] * lose[j] + win[i] * dp[j]
    vector<db> dp(n) ;
    dp[n - 1] = p[n - 1] * n ;
    vector<vec> v ;
    auto add = [&](int id)
    {
        db x = 1.0 - p[id] ;
        db y = dp[id] ;
        vec v3 = {x , y} ;
        while(v.size() >= 2)
        {
            vec v2 = v.back() ; v.pop_back() ;
            vec v1 = v.back() ;
            if(sgn(cross(v2 - v1 , v3 - v2)) >= 0)
            {
                v.push_back(v2) ;
                break ;
            }
        }
        v.push_back(v3) ;
    } ;
    add(n - 1) ;
    for(int i = n - 2 ; i >= 0 ; i --)
    {
        vec now = {p[i] * (i + 1) , p[i]} ;
        int l = 0 , r = v.size() - 1 ;
        auto cal = [&](int id)
        {
            return dot(v[id] , now) ;
        } ;
        while(r - l >= 5)
        {
            db lmid = (2 * l + r) / 3 ;
            db rmid = (2 * r + l + 2) / 3 ;
            if(cal(lmid) >= cal(rmid))  r = rmid - 1 ;
            else  l = lmid + 1 ;
        }
        for(int j = l ; j <= r ; j ++)  dp[i] = max(dp[i] , dot(now , v[j])) ;
        add(i) ;
    }
    cout << fixed << setprecision(12) << *max_element(dp.begin() , dp.end()) << '\n' ;
}
int main()
{
    std::ios::sync_with_stdio(false) , cin.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: 0ms
memory: 3720kb

input:

5
0.9 0.85 0.6 0.456000 0.000000017

output:

2.475200006589

result:

ok found '2.4752000', expected '2.4752000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

1
0.000000001

output:

0.000000001000

result:

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

Test #3:

score: 0
Accepted
time: 0ms
memory: 4000kb

input:

2
0.828496829 0.645649353

output:

1.363415270606

result:

ok found '1.3634153', expected '1.3634153', error '0.0000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 4016kb

input:

3
0.551197930 0.393255768 0.207104323

output:

0.867956505597

result:

ok found '0.8679565', expected '0.8679565', error '0.0000000'

Test #5:

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

input:

4
0.795361966 0.464795612 0.331129862 0.063526593

output:

1.338829040057

result:

ok found '1.3388290', expected '1.3388290', error '0.0000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

5
0.895888800 0.546833708 0.412641158 0.222811308 0.111288348

output:

1.726785711701

result:

ok found '1.7267857', expected '1.7267857', error '0.0000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 4004kb

input:

6
0.980827003 0.951772494 0.903718587 0.460647740 0.409951573 0.403255978

output:

3.825938315957

result:

ok found '3.8259383', expected '3.8259383', error '0.0000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

7
0.964710946 0.660694845 0.569051685 0.519424206 0.347976236 0.103554534 0.003582098

output:

2.660483845894

result:

ok found '2.6604838', expected '2.6604838', error '0.0000000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

10
0.908256456 0.813576564 0.742549305 0.649326027 0.554646135 0.461422857 0.372638782 0.277958891 0.183440845 0.094656770

output:

3.465133268121

result:

ok found '3.4651333', expected '3.4651333', error '0.0000000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

14
0.965125864 0.957983158 0.894060589 0.767619278 0.708280001 0.562719570 0.524554410 0.428166908 0.332545137 0.257543419 0.171522463 0.080323478 0.048170500 0.020758694

output:

4.986812883512

result:

ok found '4.9868129', expected '4.9868129', error '0.0000000'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

20
0.999312308 0.993123094 0.792022793 0.785833579 0.773356911 0.773356910 0.760880241 0.710678846 0.707633359 0.706159736 0.706159735 0.705865010 0.705177319 0.680125741 0.655074164 0.604872769 0.604185078 0.403084776 0.402397085 0.000098242

output:

11.722910896183

result:

ok found '11.7229109', expected '11.7229109', error '0.0000000'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

35
0.999999999 0.500000000 0.333333333 0.250000000 0.200000000 0.166666667 0.142857143 0.125000000 0.111111111 0.100000000 0.090909091 0.083333333 0.076923077 0.071428571 0.066666667 0.062500000 0.058823529 0.055555556 0.052631579 0.050000000 0.047619048 0.045454545 0.043478261 0.041666667 0.0400000...

output:

1.971428577633

result:

ok found '1.9714286', expected '1.9714286', error '0.0000000'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

42
0.999999997 0.999999957 0.999999558 0.999995984 0.999967570 0.999770574 0.998606056 0.992914780 0.970865633 0.906613334 0.772832688 0.578915971 0.379098588 0.222796093 0.121846038 0.063881487 0.032730211 0.016569178 0.008336477 0.004181321 0.002093945 0.001047795 0.000524103 0.000262103 0.0001310...

output:

11.074111636681

result:

ok found '11.0741116', expected '11.0741116', error '0.0000000'

Test #14:

score: 0
Accepted
time: 0ms
memory: 4004kb

input:

50
0.991131730 0.919779550 0.909523499 0.902541075 0.893803502 0.838347025 0.830500600 0.816318610 0.806306448 0.805684783 0.804210835 0.798232009 0.789231219 0.781205446 0.770460902 0.721836276 0.721271617 0.714886066 0.706142418 0.691410488 0.679542322 0.679399638 0.638774737 0.631666488 0.5962186...

output:

18.746675716668

result:

ok found '18.7466757', expected '18.7466757', error '0.0000000'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

75
0.720531716 0.718707013 0.709343553 0.694459021 0.689578156 0.682674306 0.679584797 0.678491929 0.670621566 0.666003031 0.665315768 0.659922689 0.659583167 0.658225062 0.658114386 0.653584609 0.649780198 0.639566830 0.636645846 0.630488992 0.628876218 0.628515225 0.615173462 0.613656515 0.6100964...

output:

21.997695508059

result:

ok found '21.9976955', expected '21.9976955', error '0.0000000'

Test #16:

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

input:

99
0.999999999 0.991828371 0.983639875 0.975434302 0.967211435 0.958971054 0.950712932 0.942436838 0.934142534 0.925829777 0.917498319 0.909147903 0.900778269 0.892389147 0.883980263 0.875551333 0.867102067 0.858632167 0.850141328 0.841629234 0.833095563 0.824539982 0.815962149 0.807361713 0.7987383...

output:

35.862420653994

result:

ok found '35.8624207', expected '35.8624207', error '0.0000000'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

150
0.999999999 0.999999998 0.999999997 0.999999996 0.999999995 0.999999994 0.999999993 0.999999992 0.999999991 0.99999999 0.999999989 0.999999988 0.999999987 0.999999986 0.999999985 0.999999984 0.999999983 0.999999982 0.999999981 0.99999998 0.999999979 0.999999978 0.999999977 0.999999976 0.99999997...

output:

63.222334038287

result:

ok found '63.2223340', expected '63.2223340', error '0.0000000'

Test #18:

score: 0
Accepted
time: 0ms
memory: 4032kb

input:

300
0.999999999 0.707106781 0.577350269 0.500000000 0.447213595 0.408248290 0.377964473 0.353553391 0.333333333 0.316227766 0.301511345 0.288675135 0.277350098 0.267261242 0.258198890 0.250000000 0.242535625 0.235702260 0.229415734 0.223606798 0.218217890 0.213200716 0.208514414 0.204124145 0.200000...

output:

18.262773054737

result:

ok found '18.2627731', expected '18.2627731', error '0.0000000'

Test #19:

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

input:

1000
0.999963957 0.999207697 0.999118706 0.997891974 0.994768087 0.990015892 0.989383451 0.987882675 0.987414725 0.986968311 0.986227809 0.985662929 0.985106306 0.983544346 0.982602847 0.981634680 0.980590743 0.978325691 0.977878867 0.977742455 0.974366243 0.972436723 0.972370267 0.972283135 0.97127...

output:

314.248999866927

result:

ok found '314.2489999', expected '314.2489999', error '0.0000000'

Test #20:

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

input:

1234
0.999999999 0.999999998 0.999999997 0.999999996 0.999999995 0.999999994 0.999999993 0.999999992 0.999999991 0.99999999 0.999999989 0.999999988 0.999999987 0.999999986 0.999999985 0.999999984 0.999999983 0.999999982 0.999999981 0.99999998 0.999999979 0.999999978 0.999999977 0.999999976 0.9999999...

output:

954.663514488509

result:

ok found '954.6635145', expected '954.6635145', error '0.0000000'

Test #21:

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

input:

3000
0.999479046 0.999467644 0.999384041 0.998543297 0.998530995 0.998473219 0.998371918 0.997799207 0.997737486 0.996491143 0.996240960 0.995286006 0.994641002 0.994623139 0.994477752 0.994465945 0.994343783 0.993985630 0.993841254 0.993633501 0.993625451 0.993495246 0.993371638 0.993313042 0.99251...

output:

934.613452337382

result:

ok found '934.6134523', expected '934.6134523', error '0.0000000'

Test #22:

score: 0
Accepted
time: 4ms
memory: 4196kb

input:

10000
0.999999999 0.999999998 0.999999997 0.999999996 0.999999995 0.999999994 0.999999993 0.999999992 0.999999991 0.999999990 0.999999989 0.999999988 0.999999987 0.999999986 0.999999985 0.999999984 0.999999983 0.999999982 0.999999981 0.999999980 0.999999979 0.999999978 0.954488188 0.876604603 0.8078...

output:

29.189038043790

result:

ok found '29.1890380', expected '29.1890380', error '0.0000000'

Test #23:

score: 0
Accepted
time: 7ms
memory: 3788kb

input:

23555
0.999818911 0.999779383 0.999771707 0.999753903 0.999742135 0.999733246 0.999717661 0.999712926 0.999652283 0.999647616 0.999638618 0.999560822 0.999556789 0.999499466 0.999489721 0.999475268 0.999454593 0.999447586 0.999438520 0.999435065 0.999417583 0.999402401 0.999400167 0.999400098 0.9993...

output:

7396.227922190849

result:

ok found '7396.2279222', expected '7396.2279222', error '0.0000000'

Test #24:

score: 0
Accepted
time: 11ms
memory: 3856kb

input:

33333
0.999998516 0.999989382 0.999956277 0.999903321 0.999893982 0.999885155 0.999833175 0.999817408 0.999814615 0.999766219 0.999763276 0.999699760 0.999670993 0.999640968 0.999610071 0.999573638 0.999566420 0.999482175 0.999434538 0.999420310 0.999389080 0.999376248 0.999369994 0.999368427 0.9993...

output:

10263.199349936343

result:

ok found '10263.1993499', expected '10263.1993499', error '0.0000000'

Test #25:

score: 0
Accepted
time: 36ms
memory: 6756kb

input:

90875
0.999999999 0.999999998 0.999999997 0.999999996 0.999999995 0.999999994 0.999999993 0.999999992 0.999999991 0.999999990 0.999999989 0.999999988 0.999999987 0.999999986 0.999999985 0.999999984 0.999999983 0.999999982 0.999999981 0.999999980 0.999999979 0.999999978 0.999999977 0.999999976 0.9999...

output:

89310.244826015114

result:

ok found '89310.2448260', expected '89310.2448260', error '0.0000000'

Test #26:

score: -100
Wrong Answer
time: 38ms
memory: 5580kb

input:

100000
0.999988194 0.999982288 0.999970500 0.999958782 0.999946973 0.999935185 0.999929279 0.999917653 0.999907318 0.999901412 0.999889647 0.999889646 0.999878573 0.999866855 0.999860949 0.999849161 0.999849160 0.999837533 0.999837532 0.999825733 0.999814014 0.999808108 0.999797773 0.999785968 0.999...

output:

30691.079303763010

result:

wrong answer 1st numbers differ - expected: '30691.8126127', found: '30691.0793038', error = '0.0000239'