QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#841957 | #9966. High Jump | ucup-team3555# | WA | 2ms | 10116kb | C++20 | 1.3kb | 2025-01-04 09:10:48 | 2025-01-04 09:10:49 |
Judging History
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,1,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: 10116kb
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: 1ms
memory: 10076kb
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: 10020kb
input:
2 0.828496829 0.645649353
output:
1.291298706000
result:
wrong answer 1st numbers differ - expected: '1.3634153', found: '1.2912987', error = '0.0528941'