QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#69142#5170. 加速度Zesty_Fox50 112ms3760kbC++202.0kb2022-12-24 10:56:412022-12-24 10:56:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-24 10:56:43]
  • 评测
  • 测评结果:50
  • 用时:112ms
  • 内存:3760kb
  • [2022-12-24 10:56:41]
  • 提交

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-6;

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;}

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();

    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++){
            db vmi,vmx,tmi,tmx;
            if(L[i]>=L[j]) vmx=1e18,tmi=-1e18;
            else vmx=calc_v(s[j]-s[i],L[j]-L[i],a),tmi=(L[j]-L[i])-calc_t(s[j]-s[i],0,a);
            if(L[i]>=R[j]) {puts("kaibai");exit(0);}
            else vmi=calc_v(s[j]-s[i],R[j]-L[i],a),tmx=(R[j]-L[i])-calc_t(s[j]-s[i],0,a);

            v0l=max(v0l,vmi),v0r=min(v0r,vmx);
            t0l=max(t0l,tmi),t0r=min(t0r,tmx);
            if(v0l<=v0r&&v0r<=f[i]&&fabs(v0r-vmx)<eps)
                f[j]=max(f[j],v0r+(db)(L[j]-L[i])*a);
            if(t0l<=t0r&&fabs(t0l-tmi)<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(v0r>=0&&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-eps>R[n]) puts("kaibai");
    else printf("%.7lf\n",ans);
    return 0;
}

詳細信息

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 2ms
memory: 3688kb

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: 2ms
memory: 3544kb

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: 0ms
memory: 3552kb

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: 3540kb

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: 0ms
memory: 3636kb

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: 2ms
memory: 3492kb

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: 20
Accepted

Test #7:

score: 20
Accepted
time: 2ms
memory: 3540kb

input:

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

output:

29.6411876

result:

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

Test #8:

score: 0
Accepted
time: 53ms
memory: 3672kb

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.2777897

result:

ok found '100.27779', expected '100.27779', error '0.00000'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3492kb

input:

3 300
0 44 217 225
0 1000000000
1 1000000000
1 1000000000
1 1000000000

output:

1.6831423

result:

ok found '1.68314', expected '1.68314', error '0.00000'

Test #10:

score: 0
Accepted
time: 3ms
memory: 3552kb

input:

3 300
0 211 253 273
0 1000000000
1 1000000000
1 1000000000
1 1000000000

output:

1.3490738

result:

ok found '1.34907', expected '1.34907', error '0.00000'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3596kb

input:

3 2
0 7 21 26
0 1000000000
1 1000000000
1 1000000000
1 1000000000

output:

5.0990195

result:

ok found '5.09902', expected '5.09902', error '0.00000'

Test #12:

score: 0
Accepted
time: 2ms
memory: 3760kb

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.2888164

result:

ok found '5.28882', expected '5.28882', error '0.00000'

Test #13:

score: 0
Accepted
time: 112ms
memory: 3580kb

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.1290837

result:

ok found '32.12908', expected '32.12908', error '0.00000'

Test #14:

score: 0
Accepted
time: 54ms
memory: 3716kb

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.0183873

result:

ok found '707.01839', expected '707.01839', error '0.00000'

Test #15:

score: 0
Accepted
time: 2ms
memory: 3756kb

input:

3 2
0 7 11 22
0 1000000000
1 1000000000
1 1000000000
1 1000000000

output:

4.6904158

result:

ok found '4.69042', expected '4.69042', error '0.00000'

Test #16:

score: 0
Accepted
time: 2ms
memory: 3632kb

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.3284780

result:

ok found '5.32848', expected '5.32848', error '0.00000'

Subtask #3:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #17:

score: 30
Accepted
time: 2ms
memory: 3660kb

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: 2ms
memory: 3592kb

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: 2ms
memory: 3496kb

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: 3400kb

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:

100%
Accepted

Dependency #3:

0%