QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#841960#9966. High Jumpucup-team3555#WA 2ms10112kbC++201.3kb2025-01-04 09:13:442025-01-04 09:13:44

Judging History

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

  • [2025-01-04 09:13:44]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10112kb
  • [2025-01-04 09:13:44]
  • 提交

answer

/*

*/

# include <bits/stdc++.h>

const int N=500010,INF=0x3f3f3f3f;

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-') f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}

typedef long double ld;

int n;
ld p[N];
ld f[N];

inline int lc(int x){
	return x<<1;
}
inline int rc(int x){
	return x<<1|1;
}

struct Line{
	ld k,b;
	inline ld val(int x){
		return k*x+b;
	}
}li[N];
int lcnt;

int tr[N<<2];

void ins(int k,int l,int r,int id){
	if(!tr[k]) return tr[k]=id,void();
	int mid=(l+r)>>1;
	if(li[tr[k]].val(mid)<li[id].val(mid)) std::swap(tr[k],id);
	if(l==r) return;
	if(li[tr[k]].val(l)<li[id].val(l)) ins(lc(k),l,mid,id);
	if(li[tr[k]].val(r)<li[id].val(r)) ins(rc(k),mid+1,r,id);
}
inline ld query(int k,int l,int r,int x){
	if(!tr[k]) return 0;
	if(l==r) return li[tr[k]].val(x);
	int mid=(l+r)>>1;
	return std::max(li[tr[k]].val(x),x<=mid?query(lc(k),l,mid,x):query(rc(k),mid+1,r,x));
}

int main(void){
	n=read();
	for(int i=1;i<=n;++i) scanf("%Lf",&p[i]);

	li[lcnt=1]={1,0},ins(1,0,n,1);
	for(int i=n;i>=0;--i){
		f[i]=query(1,0,n,i);
		if(i) li[++lcnt]={1-p[i],p[i]*f[i]},ins(1,1,n,lcnt);
	}

	printf("%.12Lf",f[0]);

	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 10064kb

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: 2ms
memory: 10040kb

input:

1
0.000000001

output:

0.000000000000

result:

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

Test #3:

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

input:

2
0.828496829 0.645649353

output:

1.291298706000

result:

wrong answer 1st numbers differ - expected: '1.3634153', found: '1.2912987', error = '0.0528941'