QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#67597 | #5170. 加速度 | skicean | 0 | 0ms | 0kb | C++14 | 2.1kb | 2022-12-10 19:44:37 | 2022-12-10 19:44:38 |
Judging History
answer
#include <cstdio>
#include <iostream>
#include <cmath>
#define macro_expand(x) #x
#define print_macro(x) printf("%s\n",macro_expand(x))
#define FOR(i,l,r) for(int i=(l),i##ADJK=(r);i<=i##ADJK;++i)
#define ROF(i,r,l) for(int i=(r),i##ADJK=(l);i>=i##ADJK;--i)
using namespace std;
typedef long long LL;
typedef long double LD;
const int MN=5e3+5;
const LD eps=1e-9;
int N;
LD s[MN],l[MN],r[MN],a;
LD f[MN];
LD pf(LD x){return x*x;}
LD jfc(LD a,LD b,LD c){return (-b+sqrt(b*b-4.0*a*c))/2.0/a;}
int main(){
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
scanf("%d%Lf",&N,&a);
FOR(i,1,N+1)scanf("%Lf",&s[i]);
FOR(i,1,N+1)scanf("%Lf %Lf",&l[i],&r[i]);
FOR(i,2,N+1)l[i]=max(l[i-1],l[i]);
ROF(i,N,1)r[i]=min(r[i+1],r[i]);
FOR(i,1,N+1){
if(l[i]>r[i]){
printf("kaibai\n");
return 0;
}
}
r[1]=0;
LD ans=1e18;
FOR(i,1,N){
LD nl=0,nr=f[i];
FOR(j,i+1,N+1){
if(j==N+1){
LD t=jfc(0.5*a,nr,-s[N+1]+s[i]);
if(r[i]+t>r[N+1])continue;
ans=min(ans,max(l[N+1],r[i]+t));
}else{
LD vl=(l[j]>r[i]+eps)?((s[j]-s[i])/(r[j]-r[i])-0.5*a*(r[j]-r[i])):0,
vr=(l[j]>r[i]+eps)?((s[j]-s[i])/(l[j]-r[i])-0.5*a*(l[j]-r[i])):1e18;
// if(i==4&&j==5){
// cerr<<"vl:"<<vl<<" vr:"<<vr<<endl;
// cerr<<"nl:"<<nl<<" nr:"<<nr<<endl;
// }
nl=max(nl,vl),nr=min(nr,vr);
if(nl-nr>eps)break;
if(fabs(s[i]+0.5*a*pf(r[j]-r[i])+nl*(r[j]-r[i])-s[j])<=eps)
f[j]=max(f[j],nl+a*(r[j]-r[i]));
}
}
LD ntl=0,ntr=1e18;
FOR(j,i+1,N+1){
if(j==N+1){
LD nw=sqrt(2.0*(s[N+1]-s[i])/a);
LD fu=r[i]+ntl+nw;
// cerr<<"j:"<<j<<" fu:"<<fu<<endl;
if(fu>r[N+1])continue;
ans=min(ans,max(l[N+1],fu));
}else{
LD tl=l[j]-r[i]-sqrt(2*(s[j]-s[i])/a),
tr=r[j]-r[i]-sqrt(2*(s[j]-s[i])/a);
ntl=max(ntl,tl),ntr=min(ntr,tr);
if(ntl-ntr>eps)break;
LD x=r[j]-r[i]-tr;
if(fabs(s[i]+0.5*a*pf(x)-s[j])<=eps)
f[j]=max(f[j],a*x);
}
}
}
// FOR(i,1,N)cerr<<f[i]<<" ";
// cerr<<endl;
if(ans>=1e18-1)printf("kaibai\n");
else printf("%.10Lf\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
詳細信息
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
input:
4 2 0 2 8 10 12 0 1000000000 2 2 4 4 6 7 6 1000000000
output:
result:
Subtask #2:
score: 0
Dangerous Syscalls
Test #7:
score: 0
Dangerous Syscalls
input:
3 20 0 4632 5697 8786 0 1000000000 1 1000000000 1 1000000000 1 1000000000
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%