QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#860022 | #9966. High Jump | Judgelight | WA | 0ms | 8140kb | C++14 | 1.3kb | 2025-01-18 09:31:24 | 2025-01-18 09:31:25 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'