QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#662270 | #5170. 加速度 | Butanlishi | 0 | 3ms | 17472kb | C++14 | 2.2kb | 2024-10-20 22:27:44 | 2024-10-20 22:27:46 |
Judging History
answer
#include<bits/stdc++.h>
#define ld double
#define ci const int
#define ll long long
#define fo(i,l,r) for(int i=(l);i<=(r);++i)
#define fu(i,l,r) for(int i=(l);i<(r);++i)
#define fd(i,l,r) for(int i=(l);i>=(r);--i)
#define P(x) __builtin_popcount(x)
#define gcd(x,y) __gcd(x,y)
using namespace std;
ci mod=1e9+7,N=1e6+5;
const ld eps=1e-9;
const ll inf=1e18;
mt19937 rad(chrono::steady_clock::now().time_since_epoch().count());
inline ll read(){ll u=0,f=1;char o;while((o=getchar())<48||o>57)if(o=='-')f=-1;u=(o^48);while((o=getchar())>=48&&o<=57)u=(u<<1)+(u<<3)+(o^48);return u*f;}
void write(ll x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+48);}
bool ST;
ll n,s[N];
ld a,len,v,t,L[N],R[N],f[N];
ld check(ld a,ld b,ld c)
{//cout<<a<<' '<<b<<' '<<c<<' '<<sqrt(b*b-4*a*c)<<'\n';
return (-b+sqrt(b*b-4*a*c))/(2*a);
}
bool ED;
signed main()
{//cerr<<(&ST-&ED)/1048576.0<<'\n';
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
// freopen("accel.in","r",stdin);
// freopen("accel.out","w",stdout);
n=read();a=read();
fo(i,1,n+1)
{
s[i]=read();
}
fo(i,1,n+1)
{
L[i]=read(),R[i]=read();
}
memset(f,-10,sizeof(f));
f[1]=0;
L[1]=R[1]=0;
ld ans=1e9;
fo(i,1,n)
{
ld lv=0,rv=f[i],lt=0,rt=inf;
fo(j,i+1,n)
{
ld len=s[j]-s[i],dt=R[j]-R[i];
ld v=len/dt-0.5*a*dt;
ld zhi=check(a/2,0,-len);
// cout<<v<<' '<<zhi<<'\n';
if(lv<=v&&v<=rv)
{//cout<<"! "<<i<<' '<<j<<' '<<lv<<' '<<rv<<'\n';
f[j]=max(f[j],v+a*dt);
}
else if(v<0)
{
ld tt=dt-zhi;
if(lt<=tt&&tt<=rt)
{
// cout<<"@ "<<i<<' '<<j<<' '<<lt<<' '<<rt<<'\n';
f[j]=max(f[j],a*zhi);
}
}
lv=max(lv,v);
ld dt2=L[j]-R[i];
if(dt2>0)
{
rv=min(rv,len/dt2-0.5*a*dt2);
lt=max(lt,dt2-zhi);
}
rt=min(rt,dt-zhi);
// cout<<"*"<<i<<' '<<lv<<' '<<rv<<' '<<lt<<' '<<rt<<' '<<len<<'\n';
}
ld len=s[n+1]-s[i];
if(lv<=rv)
{
ans=min(ans,R[i]+check(a/2,rv,-len));
}
if(lt<=rt)
{
ans=min(ans,R[i]+lt+check(a/2,0,-len));
}
// cout<<i<<' '<<f[i]<<' '<<ans<<'\n';
}
ans=max(ans,L[n+1]);
if(ans>R[n+1])puts("kaibai");
else
{
printf("%.10Lf",ans);
}
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 17472kb
input:
4 2 0 2 8 10 12 0 1000000000 2 2 4 4 6 7 6 1000000000
output:
-nan
result:
wrong output format Expected double, but "-nan" found
Subtask #2:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 0ms
memory: 16704kb
input:
3 20 0 4632 5697 8786 0 1000000000 1 1000000000 1 1000000000 1 1000000000
output:
-nan
result:
wrong output format Expected double, but "-nan" found
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%