QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#67059 | #5170. 加速度 | OvO_Zuo | 100 ✓ | 5ms | 3884kb | C++14 | 2.0kb | 2022-12-09 21:27:19 | 2022-12-09 21:27:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=5005;
typedef long double ldb;
const ldb Inf=1e18,der=1e-10;
int n,a;
int s[N],l[N],r[N];
ldb dp[N],ans;
ldb cal(ldb x,ldb y)
{
ldb der=sqrt(4*x*x+8*y*a);
der-=2*x;
der/=2*a;
return der;
}
void sol_v(int t)
{
int i,j;
ldb vl=0,vr=dp[t],nvl,nvr,tl,tr,ss;
// cout<<t<<endl;
for(i=t+1;i<=n;i++)
{
ss=s[i]-s[t];
tl=l[i]-r[t],tr=r[i]-r[t];
// cout<<tl<<" "<<tr<<endl;
// if(tr<der) return;
nvl=(ss-0.5*a*tr*tr)/tr;
// cout<<t<<" "<<i<<" "<<nvl<<endl;
vl=max(vl,nvl);
// cout<<"ss "<<(ss-0.5*a*tl*tl)/tl<<endl;
if(tl>0) vr=min(vr,(ss-0.5*a*tl*tl)/tl);
if(vr<vl-der) return;//cout<<vl<<" "<<vr<<endl;
if(vl-der<nvl) dp[i]=max(dp[i],nvl+(ldb)tr*a);//,cout<<"ukcdoco "<<i<<" "<<nvl+(ldb)tr*a<<endl;
if(i==n) ans=min(ans,r[t]+cal(vr,s[n]-s[t]));
}
// if(i==n+1) ans=min(ans,cal(t));
}
void sol_t(int t)
{
int i,j;
ldb lt=0,rt=r[t+1]-r[t],ntl,ntr,ss;//,tt;
// cout<<rt<<endl;
for(i=t+1;i<=n;i++)
{
ss=s[i]-s[t];
ntl=sqrt(2*ss/(1.0*a));
lt=max(lt,l[i]-r[t]-ntl);
// tt=rt;
rt=min(rt,r[i]-r[t]-ntl);
// cout<<ntl<<" "<<lt<<" "<<rt<<endl;
if(rt<lt) return;
// cout<<tt<<endl;
if(rt>=(r[i]-r[t]-ntl)) dp[i]=max(dp[i],(ldb)ntl*a);//,cout<<"qwert "<<i<<" "<<ntl*a<<endl;
// tt=rt;
if(i==n) ans=min(ans,r[t]+lt+ntl);
}
// if(i==n+1) ans=min(ans,dp[t]+lt+ntl);
}
int main()
{
scanf("%d%d",&n,&a);
int i,j;
for(i=0;i<=n;i++) scanf("%d",&s[i]);
for(i=0;i<=n;i++) scanf("%d%d",&l[i],&r[i]);
for(i=1;i<=n;i++) l[i]=max(l[i],l[i-1]);
r[n+1]=0x3f3f3f3f;
for(i=n;i>=0;--i)
{
r[i]=min(r[i],r[i+1]);
// cout<<i<<" "<<r[i]<<endl;
if(l[i]>r[i])
{
puts("kaibai");
return 0;
}
}
l[0]=r[0]=0;
ans=Inf;
for(i=1;i<=n;i++) dp[i]=-Inf;
dp[0]=0;
for(i=0;i<n;i++)
{
if(dp[i]==-Inf) continue;
sol_v(i);
sol_t(i);
// for(j=1;j<=n;j++) cout<<dp[j]<<" ";
// puts("");
}
if(ans>10000000) puts("kaibai");
else printf("%.10Lf",ans);
return 0;
}
詳細信息
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 1ms
memory: 3660kb
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: 0
Accepted
time: 2ms
memory: 3564kb
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: 0
Accepted
time: 2ms
memory: 3652kb
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
Accepted
time: 2ms
memory: 3560kb
input:
4 2 0 121 484 520 628 0 1000000000 5 17 11 33 31 33 37 39
output:
37.0000000000
result:
ok found '37.00000', expected '37.00000', error '0.00000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3740kb
input:
6 3 0 216 864 901 1014 1188 1437 0 1000000000 6 18 12 36 34 35 39 41 44 45 49 50
output:
49.0000000000
result:
ok found '49.00000', expected '49.00000', error '0.00000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
10 1 0 24 98 214 380 440 622 816 1075 1296 1554 0 1000000000 6 8 13 15 20 21 13 42 37 47 47 59 60 62 62 76 74 76 80 81
output:
80.0000000000
result:
ok found '80.00000', expected '80.00000', error '0.00000'
Subtask #2:
score: 20
Accepted
Test #7:
score: 20
Accepted
time: 0ms
memory: 3560kb
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
Accepted
time: 5ms
memory: 3760kb
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.2777897389
result:
ok found '100.27779', expected '100.27779', error '0.00000'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
3 300 0 44 217 225 0 1000000000 1 1000000000 1 1000000000 1 1000000000
output:
1.6831423111
result:
ok found '1.68314', expected '1.68314', error '0.00000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
3 300 0 211 253 273 0 1000000000 1 1000000000 1 1000000000 1 1000000000
output:
1.3490737563
result:
ok found '1.34907', expected '1.34907', error '0.00000'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3492kb
input:
3 2 0 7 21 26 0 1000000000 1 1000000000 1 1000000000 1 1000000000
output:
5.0990195136
result:
ok found '5.09902', expected '5.09902', error '0.00000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3564kb
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.2888163510
result:
ok found '5.28882', expected '5.28882', error '0.00000'
Test #13:
score: 0
Accepted
time: 5ms
memory: 3884kb
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.1290836922
result:
ok found '32.12908', expected '32.12908', error '0.00000'
Test #14:
score: 0
Accepted
time: 5ms
memory: 3856kb
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.0183873139
result:
ok found '707.01839', expected '707.01839', error '0.00000'
Test #15:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
3 2 0 7 11 22 0 1000000000 1 1000000000 1 1000000000 1 1000000000
output:
4.6904157598
result:
ok found '4.69042', expected '4.69042', error '0.00000'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3560kb
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.3284779715
result:
ok found '5.32848', expected '5.32848', error '0.00000'
Subtask #3:
score: 30
Accepted
Dependency #1:
100%
Accepted
Test #17:
score: 30
Accepted
time: 2ms
memory: 3556kb
input:
121 2 0 81 324 729 1296 2025 2916 3969 5184 6561 8100 9801 10960 12191 13495 14870 16317 17837 19428 21091 22827 24634 26513 29620 32927 36434 40141 44048 48155 52462 56969 61677 66584 71691 74284 76928 79621 82365 85158 88002 90895 93839 96832 99876 102969 106612 110327 114114 117973 121905 125908 ...
output:
989.0000000000
result:
ok found '989.00000', expected '989.00000', error '0.00000'
Test #18:
score: 0
Accepted
time: 2ms
memory: 3656kb
input:
104 3 0 121 486 1076 1910 2319 2777 3746 4908 6033 7305 7359 7521 7592 7676 7682 7700 7853 8153 8515 8985 9162 9352 10464 11877 12509 13189 13521 13866 15594 17622 18680 19813 21674 23728 26437 29446 30331 31243 33129 35123 36438 37801 39556 41386 42823 44309 45434 46587 50156 53969 58462 63255 6565...
output:
548.0000000000
result:
ok found '548.00000', expected '548.00000', error '0.00000'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
228 4 0 98 392 882 932 1082 1332 1848 2560 3469 4237 5105 6073 8210 10747 13684 16137 18847 21813 26194 31060 36410 38879 41448 44118 49703 55689 62074 67044 72271 77754 86198 95219 104816 114419 124598 135353 144678 154403 164528 164626 164920 165410 165869 166429 167089 168251 169669 171343 173008...
output:
1866.0000000000
result:
ok found '1866.00000', expected '1866.00000', error '0.00000'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3540kb
input:
105 3 0 121 486 1093 1944 3037 4374 5953 7653 9596 11783 14212 16884 19800 22958 27146 31766 36819 42303 48219 54568 61348 64605 67970 71443 75025 78714 82511 86416 93448 100844 108602 116724 125208 134056 143266 152499 162096 172056 182379 193065 204114 215526 225429 235633 246136 256940 268043 279...
output:
950.6401738500
result:
ok found '950.64017', expected '950.64017', error '0.00000'
Test #21:
score: 0
Accepted
time: 2ms
memory: 3552kb
input:
136 5 0 122 490 1102 1960 3062 4410 6002 7840 11537 15954 21091 26948 33526 40823 48840 57577 63250 69244 75558 82192 89146 96420 104014 111928 120317 129112 138312 147916 157926 168341 179161 190385 197896 205587 213458 221510 229741 238152 246744 255515 266439 277684 289249 301134 313339 325864 33...
output:
1040.8381531040
result:
ok found '1040.83815', expected '1040.83815', error '0.00000'
Test #22:
score: 0
Accepted
time: 2ms
memory: 3540kb
input:
265 3 0 150 600 1350 2400 3750 4645 5648 6760 7979 9306 11179 13244 15502 17951 20593 24696 29232 34200 39600 45432 50925 56782 63001 69584 76530 82121 87956 94034 100354 106918 114453 122352 130613 139238 148225 154495 160958 167613 174460 181499 191010 200884 211121 221721 232684 241586 250731 260...
output:
2305.3964205642
result:
ok found '2305.39642', expected '2305.39642', error '0.00000'
Test #23:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
165 5 0 122 490 1102 1960 3062 4319 5822 7569 9562 11800 15402 19505 24108 29211 34814 37606 40523 43566 46733 50025 50227 50835 51847 53265 55087 56434 57961 59668 61556 63623 66782 70347 74317 78692 83472 88593 94119 100050 106386 113128 118464 124046 129873 135945 142262 142564 143472 144984 1471...
output:
1255.6908331355
result:
ok found '1255.69083', expected '1255.69083', error '0.00000'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
132 5 0 10 40 90 160 250 360 485 630 796 981 1187 1412 1764 2162 2605 3093 3626 4204 6262 8821 11880 15438 19497 24056 27779 31822 36185 40868 45872 51195 57750 64806 72362 80418 88973 98029 98231 98839 99851 101269 103091 105319 106996 108854 110891 113109 115507 118084 121595 125427 129579 134051 ...
output:
739.0000000000
result:
ok found '739.00000', expected '739.00000', error '0.00000'
Test #25:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
120 4 0 8 32 72 128 200 288 444 637 866 1131 1432 1769 2816 4119 5678 7493 9564 11891 13334 14877 16520 18263 20106 22049 23999 26049 28200 30450 32800 35251 40444 46038 52031 58425 65219 72412 76832 81397 86106 90959 95956 101097 101225 101609 102249 103145 104297 105705 105867 106353 107163 108297...
output:
734.0000000000
result:
ok found '734.00000', expected '734.00000', error '0.00000'
Test #26:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
177 2 0 36 144 324 775 1426 2277 3036 3924 4940 5762 6657 7623 8124 8643 9181 10874 12729 14746 16308 17968 19726 21221 22788 24427 25221 26033 26863 27394 27934 28482 30805 33291 35939 38054 40267 42579 43503 44446 45406 47298 49262 51299 54808 58517 62427 65807 69349 73053 75822 78690 81655 84536 ...
output:
970.0000000000
result:
ok found '970.00000', expected '970.00000', error '0.00000'
Subtask #4:
score: 20
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #27:
score: 20
Accepted
time: 4ms
memory: 3664kb
input:
4158 1 0 12 50 112 200 312 450 612 800 1012 1392 1836 2345 2917 3554 4254 5019 5847 6739 8094 9593 11236 13024 14955 17030 19250 21613 24120 25713 27370 29092 30877 32726 34640 36617 38658 40764 43300 45936 48672 51509 54445 57481 60617 63854 67190 70456 73823 77289 80856 84522 88289 92156 96122 100...
output:
35602.5793415593
result:
ok found '35602.57934', expected '35602.57934', error '0.00000'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
4266 3 0 121 486 1093 1944 3037 4374 5953 7776 9841 9878 9991 10178 10441 10778 11191 11678 12241 12878 14642 16839 19468 22529 26021 29946 34303 39092 44312 48931 53851 59070 64590 70409 76529 82948 89668 96688 102083 107670 113450 119421 125584 131940 138487 145226 152158 160908 169959 179309 1889...
output:
36429.8592556744
result:
ok found '36429.85926', expected '36429.85926', error '0.00000'
Test #29:
score: 0
Accepted
time: 4ms
memory: 3672kb
input:
4300 1 0 18 72 162 288 450 648 882 1152 1458 1800 2351 2983 3697 4491 5367 6323 7360 8479 9678 10959 10977 11031 11121 11247 11409 11607 11841 12111 12417 12759 13193 13677 14209 14791 15421 16101 16829 17607 18433 19309 20182 21104 22076 23096 24165 25284 26451 27668 28933 30247 32110 34073 36136 3...
output:
36011.0000000000
result:
ok found '36011.00000', expected '36011.00000', error '0.00000'
Test #30:
score: 0
Accepted
time: 2ms
memory: 3684kb
input:
4650 4 0 200 800 1800 3200 5000 7200 8414 9729 11144 12659 14273 15988 17760 19632 21604 23676 25848 28120 32705 37691 43077 48863 55049 61635 61733 62027 62517 63203 64085 65163 66188 67358 68672 70130 71732 73478 73550 73766 74126 74630 75278 76070 77566 79463 81760 84457 87554 91051 94808 98965 1...
output:
39626.0000000000
result:
ok found '39626.00000', expected '39626.00000', error '0.00000'
Test #31:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
4865 1 0 50 200 450 800 1250 1548 1882 2253 2659 3101 3638 4225 4861 5546 6279 6890 7537 8220 8939 9694 10472 11286 12136 13022 13944 15690 17558 19546 21656 23886 25032 26215 27434 28689 29980 31934 33969 36085 38282 40560 42296 44081 45916 47799 49732 52131 54611 57172 59815 62538 64620 66751 6893...
output:
41105.6501392290
result:
ok found '41105.65014', expected '41105.65014', error '0.00000'
Test #32:
score: 0
Accepted
time: 4ms
memory: 3752kb
input:
4411 5 0 302 1210 2722 4840 7562 10890 14822 19360 24502 30250 36602 43522 51163 59524 68605 78406 88927 100168 112129 124810 138210 152331 159048 165946 173024 180282 187719 195337 203135 211113 219270 227608 236126 252872 270339 288526 307433 327060 347407 368474 390261 412768 435995 459942 477351...
output:
37194.0000000000
result:
ok found '37194.00000', expected '37194.00000', error '0.00000'
Test #33:
score: 0
Accepted
time: 4ms
memory: 3708kb
input:
3710 4 0 50 200 450 800 1250 1800 2450 3808 5491 7498 9829 12483 15462 18765 21297 24025 26949 30069 33385 36898 40606 44444 48479 52710 57137 61760 66579 71594 80388 89759 99705 110228 121326 133001 145251 156385 168003 180106 192692 205763 219317 233356 245005 256978 269275 281896 294841 308110 32...
output:
32400.0000000000
result:
ok found '32400.00000', expected '32400.00000', error '0.00000'
Test #34:
score: 0
Accepted
time: 3ms
memory: 3720kb
input:
3770 1 0 50 200 450 800 1250 1800 2450 3200 4050 5000 6215 7574 9078 10725 12517 14452 16532 18755 21122 23634 25580 27607 29716 31905 34176 36527 38960 41473 44068 46743 50376 54154 58075 62141 66350 70704 75202 79843 84629 89558 92485 95461 98486 101560 104683 107855 111076 114346 117665 121033 12...
output:
32208.8958837472
result:
ok found '32208.89588', expected '32208.89588', error '0.00000'
Test #35:
score: 0
Accepted
time: 4ms
memory: 3872kb
input:
3840 4 0 288 1152 2592 4608 7200 10368 11738 13209 14780 16451 18222 20093 24430 29251 34556 40345 46618 53375 58172 63225 68534 74100 79921 85998 94294 103075 112340 122088 132321 143038 147834 152730 157727 162823 168020 173316 185730 198721 212288 226431 241150 256445 270304 284648 299476 314788 ...
output:
33476.0000000000
result:
ok found '33476.00000', expected '33476.00000', error '0.00000'
Test #36:
score: 0
Accepted
time: 4ms
memory: 3752kb
input:
4090 4 0 288 1152 2592 4608 7200 10368 14112 18432 23328 28800 31174 33649 36224 38899 41674 44548 47523 50598 53773 57048 64495 72427 80843 89742 99126 108994 119345 130181 141501 153304 162583 172186 182113 192365 202940 213839 225062 236610 248481 260676 267386 274196 281107 288117 295227 302438 ...
output:
34741.9230406115
result:
ok found '34741.92304', expected '34741.92304', error '0.00000'