QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#105006 | #5170. 加速度 | haoren | 20 | 47ms | 3924kb | C++14 | 1.4kb | 2023-05-12 20:07:04 | 2023-05-12 20:07:05 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int aa=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')aa=(aa<<3)+(aa<<1)+ch-'0',ch=getchar();
return aa*f;
}
const int M=5e3+10;
int n,a;
int s[M],l[M],r[M];
double f[M],ans=1e18;
main(){
n=read();a=read();for(int i=1;i<=n+1;i++) s[i]=read();for(int i=1;i<=n+1;i++) l[i]=read(),r[i]=read();r[1]=0;
for(int i=1;i<=n;i++){
double l1=0,l2=0,r1=1e18,r2=f[i];
//路径需要等待时间/提供等待时间
//路径速度限制
for(int j=i+1;j<=n;j++){
//无初速度
if(r[j]<r[i]) break;double t=sqrt(2.0*(s[j]-s[i])*1.0/(1.0*a)),wt=r[j]-r[i]-t;//等待时间
if(wt>=l1&&wt<=r1) f[j]=max(f[j],t*1.0*a);if(l[j]>r[i]) l1=max(l1,l[j]-r[i]-t);r1=min(r1,wt);
//有初速度
double v0=(s[j]-s[i])*1.0/(1.0*(r[j]-r[i]))-0.5*a*((r[j]-r[i])*1.0);
if(v0>=l2&&v0<=r2) f[j]=max(f[j],sqrt(2.0*a*(1.0*(s[j]-s[i]))+v0*v0));
if(l[j]>r[i]) r2=min(r2,(s[j]-s[i])*1.0/(1.0*(l[j]-r[i]))-0.5*a*(1.0*(l[j]-r[i])));l2=max(l2,v0);
if(j==n){
if(l1<=r1&&sqrt(2.0*(s[n+1]-s[i])*1.0/(1.0*a))+l1+r[i]<=r[n+1]) ans=min(ans,sqrt(2.0*(s[n+1]-s[i])*1.0/(1.0*a))+l1+r[i]);
if(l2<=r2){double vmax=sqrt((s[n+1]-s[i])*1.0*a*2.0+r2*r2);ans=min(ans,(vmax-r2)*1.0/(1.0*a)+r[i]);}
}
}
}
if(ans==1e18) cout<<"kaibai";
else printf("%0.6lf",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 30
Accepted
time: 2ms
memory: 3516kb
input:
4 2 0 2 8 10 12 0 1000000000 2 2 4 4 6 7 6 1000000000
output:
6.585786
result:
ok found '6.58579', expected '6.58579', error '0.00000'
Test #2:
score: -30
Wrong Answer
time: 2ms
memory: 3688kb
input:
5 1 0 1 2 3 4 5 0 1000000000 1 2 2 3 3 4 4 5 5 6
output:
4.372281
result:
wrong answer 1st numbers differ - expected: '5.00000', found: '4.37228', error = '0.12554'
Subtask #2:
score: 20
Accepted
Test #7:
score: 20
Accepted
time: 2ms
memory: 3724kb
input:
3 20 0 4632 5697 8786 0 1000000000 1 1000000000 1 1000000000 1 1000000000
output:
29.641188
result:
ok found '29.64119', expected '29.64119', error '0.00000'
Test #8:
score: 0
Accepted
time: 43ms
memory: 3644kb
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:
100.277790
result:
ok found '100.27779', expected '100.27779', error '0.00000'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3536kb
input:
3 300 0 44 217 225 0 1000000000 1 1000000000 1 1000000000 1 1000000000
output:
1.683142
result:
ok found '1.68314', expected '1.68314', error '0.00000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
3 300 0 211 253 273 0 1000000000 1 1000000000 1 1000000000 1 1000000000
output:
1.349074
result:
ok found '1.34907', expected '1.34907', error '0.00000'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3608kb
input:
3 2 0 7 21 26 0 1000000000 1 1000000000 1 1000000000 1 1000000000
output:
5.099020
result:
ok found '5.09902', expected '5.09902', error '0.00000'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3736kb
input:
300 300 0 5 26 46 67 75 77 94 103 104 115 116 120 152 156 174 184 203 212 227 248 259 269 278 279 280 300 305 319 320 328 332 357 360 360 372 380 390 404 409 409 420 441 455 464 467 467 503 511 536 553 568 575 597 602 607 622 626 632 637 645 672 673 674 680 681 688 700 705 707 710 710 730 748 753 75...
output:
5.288816
result:
ok found '5.28882', expected '5.28882', error '0.00000'
Test #13:
score: 0
Accepted
time: 46ms
memory: 3752kb
input:
5000 100 0 12 33 57 92 94 120 157 208 220 222 236 236 237 238 247 259 317 323 358 361 365 383 396 431 441 498 506 517 542 542 544 545 571 590 598 626 630 639 639 668 670 674 684 693 693 694 748 753 760 760 767 785 793 798 805 820 851 852 852 867 897 916 942 945 963 969 980 986 994 1010 1014 1019 102...
output:
32.129084
result:
ok found '32.12908', expected '32.12908', error '0.00000'
Test #14:
score: 0
Accepted
time: 47ms
memory: 3924kb
input:
5000 2 0 96 121 212 282 332 358 388 393 464 586 666 972 998 1056 1116 1117 1313 1335 1514 1538 1573 1634 1769 1816 1819 1843 1877 1881 1901 2136 2234 2248 2355 2457 2467 2559 2676 2713 3063 3137 3232 3308 3327 3334 3373 3397 3471 3634 3720 3932 3946 3959 4032 4113 4275 4491 4792 4845 4934 4987 5032 ...
output:
707.018387
result:
ok found '707.01839', expected '707.01839', error '0.00000'
Test #15:
score: 0
Accepted
time: 2ms
memory: 3708kb
input:
3 2 0 7 11 22 0 1000000000 1 1000000000 1 1000000000 1 1000000000
output:
4.690416
result:
ok found '4.69042', expected '4.69042', error '0.00000'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3520kb
input:
300 300 0 3 10 13 28 37 62 69 89 91 98 100 136 154 159 161 161 165 178 212 225 228 241 246 253 257 267 288 293 302 303 307 320 325 327 340 345 359 363 372 382 389 394 395 401 404 408 418 447 453 458 465 466 467 468 484 485 488 495 503 506 516 563 567 570 575 578 585 586 587 599 607 612 624 628 637 6...
output:
5.328478
result:
ok found '5.32848', expected '5.32848', error '0.00000'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%