QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#856658#9966. High JumpIllusionaryDominance#WA 1ms8300kbC++20879b2025-01-14 15:04:552025-01-14 15:05:04

Judging History

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

  • [2025-01-14 15:05:04]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8300kb
  • [2025-01-14 15:04:55]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500000 + 5;

int N;
long 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) -> long double {
        return (1.0 - p[j]) * i + f[j];
    };
    long 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 - 1]]) > (f[i] - f[q[tl]]) / (p[i] - p[q[tl]])) tl --;
        q[++ tl] = i;
    }
    cout << fixed << setprecision(20) << ans << '\n';
    
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 8296kb

input:

5
0.9 0.85 0.6 0.456000 0.000000017

output:

2.47520000658920000009

result:

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

Test #2:

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

input:

1
0.000000001

output:

0.00000000100000000000

result:

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

Test #3:

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

input:

2
0.828496829 0.645649353

output:

1.36341527060640163701

result:

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

Test #4:

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

input:

3
0.551197930 0.393255768 0.207104323

output:

0.86795650559748506393

result:

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

Test #5:

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

input:

4
0.795361966 0.464795612 0.331129862 0.063526593

output:

1.33882904005673202691

result:

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

Test #6:

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

input:

5
0.895888800 0.546833708 0.412641158 0.222811308 0.111288348

output:

1.72678571170068373940

result:

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

Test #7:

score: -100
Wrong Answer
time: 0ms
memory: 8168kb

input:

6
0.980827003 0.951772494 0.903718587 0.460647740 0.409951573 0.403255978

output:

3.80444552891238925809

result:

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