QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#860022#9966. High JumpJudgelightWA 0ms8140kbC++141.3kb2025-01-18 09:31:242025-01-18 09:31:25

Judging History

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

  • [2025-01-18 09:31:25]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:8140kb
  • [2025-01-18 09:31:24]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define eb emplace_back
#define mk make_pair
#define N 500009
#define db double
using namespace std;
int n;db p[N],f[N];
struct Node{int l,r;db k,b;}tr[N*4];
void build(int u,int l,int r){
	tr[u].l=l,tr[u].r=r,tr[u].b=-1e18;
	if(l==r)return ;
	int mid=(l+r)>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
inline db F(db k,db b,int x){return k*x+b;}
void mdf(int u,db k,db b){
	if(F(tr[u].k,tr[u].b,tr[u].l)>=F(k,b,tr[u].l)&&F(tr[u].k,tr[u].b,tr[u].r)>=F(k,b,tr[u].r))return ;
	if(F(tr[u].k,tr[u].b,tr[u].l)<F(k,b,tr[u].l)&&F(tr[u].k,tr[u].b,tr[u].r)<F(k,b,tr[u].r)){tr[u].k=k,tr[u].b=b;return ;}
	int mid=(tr[u].l+tr[u].r)>>1;
	if(F(tr[u].k,tr[u].b,mid)<F(k,b,mid))swap(tr[u].k,k),swap(tr[u].b,b);
	if(F(tr[u].k,tr[u].b,tr[u].l)<F(k,b,tr[u].l))mdf(u<<1,k,b);else mdf(u<<1|1,k,b);
}
db qry(int u,int x){
	if(tr[u].l==tr[u].r)return F(tr[u].k,tr[u].b,x);
	int mid=(tr[u].l+tr[u].r)>>1;
	if(x<=mid)return max(F(tr[u].k,tr[u].b,x),qry(u<<1,x));
	else return max(F(tr[u].k,tr[u].b,x),qry(u<<1|1,x)); 
}
signed main(){
	scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lf",&p[i]);
	build(1,1,n),f[n]=n;mdf(1,-p[n],p[n]*f[n]);
	for(int i=n-1;i>=0;i--){
		f[i]=i+qry(1,i),mdf(1,-p[i],p[i]*f[i]); 
	}
	printf("%.6lf",f[0]);
	return 0;
}

详细

Test #1:

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

input:

5
0.9 0.85 0.6 0.456000 0.000000017

output:

2.475200

result:

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

Test #2:

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

input:

1
0.000000001

output:

0.000000

result:

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

Test #3:

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

input:

2
0.828496829 0.645649353

output:

1.291299

result:

wrong answer 1st numbers differ - expected: '1.3634153', found: '1.2912990', error = '0.0528938'