QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662268 | #5170. 加速度 | Butanlishi | 60 | 5ms | 25660kb | C++14 | 2.2kb | 2024-10-20 22:27:16 | 2024-10-20 22:27:17 |
Judging History
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];
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);
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 0ms
memory: 24804kb
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: 5ms
memory: 24236kb
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: 5ms
memory: 25660kb
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: 30
Accepted
time: 0ms
memory: 24132kb
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: 30
Accepted
time: 0ms
memory: 24444kb
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: 30
Accepted
time: 4ms
memory: 25216kb
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: 0
Time Limit Exceeded
Test #7:
score: 20
Accepted
time: 0ms
memory: 25412kb
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: 30
Accepted
Dependency #1:
100%
Accepted
Test #17:
score: 30
Accepted
time: 2ms
memory: 24144kb
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: 30
Accepted
time: 5ms
memory: 25228kb
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: 30
Accepted
time: 0ms
memory: 25252kb
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: 30
Accepted
time: 2ms
memory: 24840kb
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: 30
Accepted
time: 5ms
memory: 24192kb
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: 30
Accepted
time: 0ms
memory: 24636kb
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: 30
Accepted
time: 0ms
memory: 25112kb
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: 30
Accepted
time: 0ms
memory: 24976kb
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: 30
Accepted
time: 0ms
memory: 23568kb
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: 30
Accepted
time: 0ms
memory: 24856kb
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: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%