QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#856635	#9966. High Jump	IllusionaryDominance^#	WA	0ms	8288kb	C++20	864b	2025-01-14 14:57:54	2025-01-14 14:58:02

Judging History

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

[2025-01-14 14:58:02]
评测

测评结果：WA
用时：0ms
内存：8288kb

查看

[2025-01-14 14:57:54]
提交

answer

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500000 + 5;

int N;
double p[MAX_N], f[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    for (int i = 1; i <= N; i ++) {
        cin >> p[i];
    }
    static int q[MAX_N];
    int hd = 0, tl = -1;
    q[++ tl] = N + 1;
    auto w = [&](int i, int j) -> double {
        return (1.0 - p[j]) * i + f[j];
    };
    double ans = 0;
    for (int i = N; i > 0; i --) {
        while (hd < tl && w(i, q[hd + 1]) > w(i, q[hd])) hd ++;
        f[i] = w(i, q[hd]) * p[i]; ans = max(ans, f[i]);
        while (tl > hd && (f[i] - f[q[tl - 1]]) * (p[i] - p[q[tl]]) > (f[i] - f[q[tl]]) * (p[i] - p[q[tl - 1]])) tl --;
        q[++ tl] = i;
    }
    cout << fixed << setprecision(12) << ans << '\n';
    
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 8160kb

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: 8064kb

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: 8284kb

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: 8160kb

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: 8160kb

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: 8156kb

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: -100

Wrong Answer

time: 0ms

memory: 8288kb

input:

6
0.980827003 0.951772494 0.903718587 0.460647740 0.409951573 0.403255978

output:

3.804445528912

result:

wrong answer 1st numbers differ - expected: '3.8259383', found: '3.8044455', error = '0.0056177'