QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#662270#5170. 加速度Butanlishi0 3ms17472kbC++142.2kb2024-10-20 22:27:442024-10-20 22:27:46

Judging History

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

  • [2024-10-20 22:27:46]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:17472kb
  • [2024-10-20 22:27:44]
  • 提交

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%