QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#856658 | #9966. High Jump | IllusionaryDominance# | WA | 1ms | 8300kb | C++20 | 879b | 2025-01-14 15:04:55 | 2025-01-14 15:05:04 |
Judging History
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'