QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#662254#5170. 加速度Butanlishi0 3ms25644kbC++142.2kb2024-10-20 22:17:572024-10-20 22:17:57

Judging History

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

  • [2024-10-20 22:17:57]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:25644kb
  • [2024-10-20 22:17:57]
  • 提交

answer

#include<bits/stdc++.h>
#define ld long 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];
			rv=min(rv,len/dt2-0.5*a*dt2);
			lt=max(lt,dt2-zhi);
			rt=min(rt,dt-zhi);
		}
		ld len=s[n+1]-s[i];
//		cout<<"*"<<lv<<' '<<rv<<' '<<lt<<' '<<rt<<' '<<len<<' '<<check(a/2,0,-len)<<'\n';
		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: 30
Accepted
time: 0ms
memory: 25360kb

input:

4 2
0 2 8 10 12
0 1000000000
2 2
4 4
6 7
6 1000000000


output:

6.5857864376

result:

ok found '6.58579', expected '6.58579', error '0.00000'

Test #2:

score: 30
Accepted
time: 0ms
memory: 25644kb

input:

5 1
0 1 2 3 4 5
0 1000000000
1 2
2 3
3 4
4 5
5 6

output:

5.0000000000

result:

ok found '5.00000', expected '5.00000', error '0.00000'

Test #3:

score: 30
Accepted
time: 0ms
memory: 23940kb

input:

2 1
0 2 8
0 1000000000
4 1000000000
0 1000000000

output:

6.0000000000

result:

ok found '6.00000', expected '6.00000', error '0.00000'

Test #4:

score: 0
Wrong Answer
time: 3ms
memory: 24196kb

input:

4 2
0 121 484 520 628
0 1000000000
5 17
11 33
31 33
37 39

output:

kaibai

result:

wrong output format Expected double, but "kaibai" found

Subtask #2:

score: 0
Time Limit Exceeded

Test #7:

score: 20
Accepted
time: 0ms
memory: 25320kb

input:

3 20
0 4632 5697 8786
0 1000000000
1 1000000000
1 1000000000
1 1000000000

output:

29.6411875606

result:

ok found '29.64119', expected '29.64119', error '0.00000'

Test #8:

score: 0
Time Limit Exceeded

input:

5000 100
0 26 289 325 425 558 844 885 1020 1186 1385 1398 1414 1444 1470 1914 1932 1956 2127 2194 2316 2339 2419 2521 2567 2647 2655 2804 3016 3053 3102 3240 3294 3491 3540 3591 3642 3680 3763 3804 3865 3955 3997 4048 4053 4100 4212 4222 4238 4302 4354 4358 4532 4534 4547 4550 4551 4695 4761 4762 48...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%