QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#860055 | #9966. High Jump | Nightmare07 | WA | 1ms | 8144kb | C++14 | 972b | 2025-01-18 09:52:25 | 2025-01-18 09:52:30 |
Judging History
answer
#include <bits/stdc++.h>
#define i64 long long
using namespace std;
const int N = 5e5 + 10;
int n, hh, tt = -1;
pair<double, double> q[N];
double p[N], f[N];
double solve(pair<double, double> a, int i) {
return a.second + a.first * i;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++) scanf("%lf", &p[i]);
for (int i = 1; i <= n + 1; i ++) p[i] = 1 - p[i];
f[n + 1] = 0;
q[++ tt] = make_pair(p[n + 1], f[n + 1]);
for (int i = n; i >= 1; i --) {
while (hh + 1 <= tt && solve(q[tt - 1], i) > solve(q[tt], i)) tt --;
f[i] = solve(q[tt], i) * (1 - p[i]);
pair<double, double> Nw = make_pair(p[i], f[i]);
while (hh + 1 <= tt &&
(Nw.second - q[tt].second) * (q[tt].first - q[tt - 1].first) <
(q[tt].second - q[tt - 1].second) * (Nw.first - q[tt].first)
) tt --;
q[++ tt] = Nw;
}
double ans = 0;
for (int i = 1; i <= n; i ++) ans = max(ans, f[i]);
printf("%.9lf", ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 8140kb
input:
5 0.9 0.85 0.6 0.456000 0.000000017
output:
2.475200007
result:
ok found '2.4752000', expected '2.4752000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 8008kb
input:
1 0.000000001
output:
0.000000001
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 8144kb
input:
2 0.828496829 0.645649353
output:
1.363415271
result:
ok found '1.3634153', expected '1.3634153', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 8140kb
input:
3 0.551197930 0.393255768 0.207104323
output:
0.867956506
result:
ok found '0.8679565', expected '0.8679565', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 8016kb
input:
4 0.795361966 0.464795612 0.331129862 0.063526593
output:
1.338829040
result:
ok found '1.3388290', expected '1.3388290', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 8008kb
input:
5 0.895888800 0.546833708 0.412641158 0.222811308 0.111288348
output:
1.726785712
result:
ok found '1.7267857', expected '1.7267857', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 7972kb
input:
6 0.980827003 0.951772494 0.903718587 0.460647740 0.409951573 0.403255978
output:
3.825938316
result:
ok found '3.8259383', expected '3.8259383', error '0.0000000'
Test #8:
score: -100
Wrong Answer
time: 1ms
memory: 8012kb
input:
7 0.964710946 0.660694845 0.569051685 0.519424206 0.347976236 0.103554534 0.003582098
output:
2.342384298
result:
wrong answer 1st numbers differ - expected: '2.6604838', found: '2.3423843', error = '0.1195645'