QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#860055#9966. High JumpNightmare07WA 1ms8144kbC++14972b2025-01-18 09:52:252025-01-18 09:52:30

Judging History

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

  • [2025-01-18 09:52:30]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8144kb
  • [2025-01-18 09:52:25]
  • 提交

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'