QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#69132 | #5170. 加速度 | Zesty_Fox | 30 | 3ms | 8000kb | C++20 | 2.6kb | 2022-12-24 10:38:50 | 2022-12-24 10:38:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64=long long;
using db=double;
using vi=vector<int>;
using pii=pair<int,int>;
template<typename T>
inline T read(){
T x=0,f=0;char ch=getchar();
while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
while(isdigit(ch)) x=(x*10)+(ch^48),ch=getchar();
return !f?x:-x;
}
#define rdi read<int>
#define rdi64 read<i64>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
const int N=5010;
const db eps=1e-7;
int n,a,s[N];
int L[N],R[N];
db f[N];
db calc_v(db s,db t,db a) {return (2*s-a*t*t)/(2*t);}
db calc_t(db s,db v0,db a) {return (sqrt(v0*v0+2*s*a)-v0)/a;}
// 最大初速度 最小等待时间
db vmx[N][N], tmi[N][N];
// 最小初速度 最大等待时间
db vmi[N][N], tmx[N][N];
void init(){
for(int i=0;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(L[i]>=L[j]){
vmx[i][j]=1e18;
tmi[i][j]=-1e18;
}
else{
vmx[i][j]=calc_v(s[j]-s[i],L[j]-L[i],a);
tmi[i][j]=(L[j]-L[i])-calc_t(s[j]-s[i],0,a);
if(tmi[i][j]<-eps) tmi[i][j]=-1e18;
}
if(L[i]>=R[j]){
puts("kaibai");
exit(0);
}
else{
vmi[i][j]=calc_v(s[j]-s[i],R[j]-L[i],a);
tmx[i][j]=(R[j]-L[i])-calc_t(s[j]-s[i],0,a);
if(tmx[i][j]<-eps) tmx[i][j]=-1e18;
}
}
}
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
n=rdi(),a=rdi();
for(int i=0;i<=n;i++) s[i]=rdi();
for(int i=0;i<=n;i++) L[i]=rdi(),R[i]=rdi();
init();
db ans=1e18;
for(int i=1;i<=n;i++) f[i]=-1e18;
f[0]=0;
for(int i=0;i<=n;i++){
db v0l=0,v0r=f[i];
db t0l=0,t0r=1e18;
for(int j=i+1;j<=n;j++){
v0l=max(v0l,vmi[i][j]),v0r=min(v0r,vmx[i][j]);
t0l=max(t0l,tmi[i][j]),t0r=min(t0r,tmx[i][j]);
if(v0l<=v0r&&v0r<=f[i]&&fabs(v0r-vmx[i][j])<eps)
f[j]=max(f[j],v0r+(db)(L[j]-L[i])*a);
if(t0l<=t0r&&fabs(t0l-tmi[i][j])<eps)
f[j]=max(f[j],(L[j]-L[i]-t0l)*a);
}
if(i<n){
if(v0l<=v0r)
ans=min(ans,L[i]+calc_t(s[n]-s[i],v0r,a));
if(t0l<=t0r)
ans=min(ans,L[i]+t0l+calc_t(s[n]-s[i],0,a));
}
}
if(f[n]>=0) ans=L[n];
if(ans>1e9) puts("kaibai");
else printf("%.7lf\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 3ms
memory: 3692kb
input:
4 2 0 2 8 10 12 0 1000000000 2 2 4 4 6 7 6 1000000000
output:
6.5857864
result:
ok found '6.58579', expected '6.58579', error '0.00000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
5 1 0 1 2 3 4 5 0 1000000000 1 2 2 3 3 4 4 5 5 6
output:
5.0000000
result:
ok found '5.00000', expected '5.00000', error '0.00000'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3688kb
input:
2 1 0 2 8 0 1000000000 4 1000000000 0 1000000000
output:
6.0000000
result:
ok found '6.00000', expected '6.00000', error '0.00000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3696kb
input:
4 2 0 121 484 520 628 0 1000000000 5 17 11 33 31 33 37 39
output:
37.0000000
result:
ok found '37.00000', expected '37.00000', error '0.00000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3720kb
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.0000000
result:
ok found '49.00000', expected '49.00000', error '0.00000'
Test #6:
score: 0
Accepted
time: 3ms
memory: 7808kb
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.0000000
result:
ok found '80.00000', expected '80.00000', error '0.00000'
Subtask #2:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 2ms
memory: 3680kb
input:
3 20 0 4632 5697 8786 0 1000000000 1 1000000000 1 1000000000 1 1000000000
output:
18.5755512
result:
wrong answer 1st numbers differ - expected: '29.64119', found: '18.57555', error = '0.37332'
Subtask #3:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #17:
score: 30
Accepted
time: 1ms
memory: 5796kb
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.0000000
result:
ok found '989.00000', expected '989.00000', error '0.00000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 7368kb
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.0000000
result:
ok found '548.00000', expected '548.00000', error '0.00000'
Test #19:
score: 0
Accepted
time: 1ms
memory: 8000kb
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.0000000
result:
ok found '1866.00000', expected '1866.00000', error '0.00000'
Test #20:
score: -30
Wrong Answer
time: 3ms
memory: 5252kb
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:
kaibai
result:
wrong output format Expected double, but "kaibai" found
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%