QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#454306#5170. 加速度szzjz60 3ms4052kbC++141.8kb2024-06-24 19:08:322024-06-24 19:08:38

Judging History

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

  • [2024-06-24 19:08:38]
  • 评测
  • 测评结果:60
  • 用时:3ms
  • 内存:4052kb
  • [2024-06-24 19:08:32]
  • 提交

answer

#include<bits/stdc++.h>
#define fi first
#define se second
#define mk make_pair
#define pub emplace_back
#define pob pop_back
using namespace std;
const int N=5010;
typedef long double ld;
int n;ld a,s[N],rg[N][2];
ld dp[N][2];
ld solve(ld x,ld y,ld z){
	if(y*y-4*x*z<0) return -1e9;
	return (-y+sqrt(y*y-4*x*z))/(2*x);
}
bool check(int st,int ed,ld v0,ld bas){
	for(int k=st+1;k<=ed;k++){
		ld tt=solve(a/2,v0,s[st]-s[k])+bas;
	//	cout<<st<<"->"<<ed<<":"<<k<<" "<<tt<<endl;
		if(rg[k][0]>tt||rg[k][1]<tt) return 0;
	}
	return 1;
}
int main(){
//	auto file1=freopen("dd.in","r",stdin);
	cin>>n>>a;n++;
	for(int i=1;i<=n;i++) cin>>s[i];
	for(int i=1;i<=n;i++) cin>>rg[i][0]>>rg[i][1];
	dp[1][0]=dp[1][1]=0;
	ld ans=1e12;
	for(int i=2;i<=n;i++){
		for(int opi=0;opi<=1;opi++){
			dp[i][opi]=-1e9;
			for(int j=1;j<i;j++){
				for(int opj=0;opj<=1;opj++){
					if(dp[j][opj]<0) continue;
					ld tl=rg[j][opj],tr=rg[i][opi];
					ld x=s[i]-s[j];ld t=sqrt(x*2/a);
					if(t<=tr-tl){
						bool ok=1;
						for(int k=j+1;k<i;k++){
							ld tt=sqrt(2*(s[k]-s[j])/a)+tr-t;
							if(rg[k][0]>tt||rg[k][1]<tt){
								ok=0;
								break;
							}
						//	cout<<j<<" "<<k<<" "<<i<<" "<<tt<<endl;
						}
						if(ok) dp[i][opi]=max(dp[i][opi],t*a);
					}else{
						ld v0=(x-(tr-tl)*(tr-tl)/2*a)/(tr-tl);
						if(v0>=0&&v0<=dp[j][opj]&&check(j,i-1,v0,rg[j][opj])){
							dp[i][opi]=max(dp[i][opi],2*x/(tr-tl)-v0);
						}
					}
				}
			}
		//	cout<<i<<","<<opi<<":"<<dp[i][opi]<<endl;
			if(dp[i][opi]<0) continue;
			if(i==n) ans=min(ans,rg[i][opi]);
			else{
				ld v=dp[i][opi];
				if(check(i,n,v,rg[i][opi])){
					ld tt=solve(a/2,v,s[i]-s[n]);
			//		cout<<"suc:"<<i<<" "<<v<<" "<<rg[i][opi]<<"+"<<tt<<endl;
					ans=min(ans,rg[i][opi]+tt);
				}
			}
		}
	}
	printf("%0.5Lf",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: 0ms
memory: 3784kb

input:

4 2
0 2 8 10 12
0 1000000000
2 2
4 4
6 7
6 1000000000


output:

6.58579

result:

ok found '6.58579', expected '6.58579', error '0.00000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3932kb

input:

5 1
0 1 2 3 4 5
0 1000000000
1 2
2 3
3 4
4 5
5 6

output:

5.00000

result:

ok found '5.00000', expected '5.00000', error '0.00000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4036kb

input:

2 1
0 2 8
0 1000000000
4 1000000000
0 1000000000

output:

6.00000

result:

ok found '6.00000', expected '6.00000', error '0.00000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3932kb

input:

4 2
0 121 484 520 628
0 1000000000
5 17
11 33
31 33
37 39

output:

37.00000

result:

ok found '37.00000', expected '37.00000', error '0.00000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 4020kb

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

result:

ok found '49.00000', expected '49.00000', error '0.00000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 4000kb

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

result:

ok found '80.00000', expected '80.00000', error '0.00000'

Subtask #2:

score: 0
Wrong Answer

Test #7:

score: 0
Wrong Answer
time: 0ms
memory: 4020kb

input:

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

output:

1000000000.00000

result:

wrong answer 1st numbers differ - expected: '29.64119', found: '1000000000.00000', error = '33736838.92774'

Subtask #3:

score: 30
Accepted

Dependency #1:

100%
Accepted

Test #17:

score: 30
Accepted
time: 0ms
memory: 3896kb

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

result:

ok found '989.00000', expected '989.00000', error '0.00000'

Test #18:

score: 0
Accepted
time: 1ms
memory: 3860kb

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

result:

ok found '548.00000', expected '548.00000', error '0.00000'

Test #19:

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

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

result:

ok found '1866.00000', expected '1866.00000', error '0.00000'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3928kb

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

result:

ok found '950.64017', expected '950.64017', error '0.00000'

Test #21:

score: 0
Accepted
time: 1ms
memory: 3936kb

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

result:

ok found '1040.83815', expected '1040.83815', error '0.00000'

Test #22:

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

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

result:

ok found '2305.39642', expected '2305.39642', error '0.00000'

Test #23:

score: 0
Accepted
time: 1ms
memory: 3872kb

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

result:

ok found '1255.69083', expected '1255.69083', error '0.00000'

Test #24:

score: 0
Accepted
time: 1ms
memory: 3856kb

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

result:

ok found '739.00000', expected '739.00000', error '0.00000'

Test #25:

score: 0
Accepted
time: 1ms
memory: 3984kb

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

result:

ok found '734.00000', expected '734.00000', error '0.00000'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3796kb

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

result:

ok found '970.00000', expected '970.00000', error '0.00000'

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%