QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#507492#2338. Beautiful BridgesflyingTL 1ms6072kbC++14842b2024-08-06 18:19:402024-08-06 18:19:40

Judging History

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

  • [2024-08-06 18:19:40]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:6072kb
  • [2024-08-06 18:19:40]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e4+5;

int dp[N], x[N], y[N], n, h;
bool can[N][N];

int dist(int x1,int y1,int x2,int y2)
{
	return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
}

bool check(int l,int r)
{
	int lim=2*h-(x[r]-x[l]);
	for(int i=l;i<=r;i++)
		if(y[i]*2>lim && dist(x[i]*2,y[i]*2,x[l]+x[r],lim)>(x[r]-x[l])*(x[r]-x[l]))
			return false;
	return true;
}

signed main()
{
	int a,b;
	cin >> n >> h >> a >> b;
	for(int i=1;i<=n;i++)
		scanf("%lld %lld",&x[i],&y[i]);

	memset(dp,0x3f,sizeof(dp));
	dp[1]=a*(h-y[1]);
	for(int i=2;i<=n;i++)
		for(int j=i-1;j>=1;j--)
			if(check(j,i))
				dp[i]=min(dp[i],dp[j]+a*(h-y[i])+b*(x[i]-x[j])*(x[i]-x[j]));

	if(dp[n]==0x3f3f3f3f3f3f3f3f)
		printf("impossible\n");
	else
		printf("%lld\n",dp[n]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5888kb

input:

5 60 18 2
0 0
20 20
30 10
50 30
70 20

output:

6460

result:

ok single line: '6460'

Test #2:

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

input:

4 10 1 1
0 0
1 9
9 9
10 0

output:

impossible

result:

ok single line: 'impossible'

Test #3:

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

input:

2 1 1 1
0 0
2 0

output:

6

result:

ok single line: '6'

Test #4:

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

input:

2 1 1 1
0 0
3 0

output:

impossible

result:

ok single line: 'impossible'

Test #5:

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

input:

4 5 100 1
0 0
1 3
9 3
10 0

output:

1100

result:

ok single line: '1100'

Test #6:

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

input:

4 5 1 100
0 0
1 3
9 3
10 0

output:

10010

result:

ok single line: '10010'

Test #7:

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

input:

2 100000 10000 10000
0 0
100000 0

output:

100002000000000

result:

ok single line: '100002000000000'

Test #8:

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

input:

13 43 1 5
3 26
4 25
10 23
11 0
23 2
49 20
64 2
68 0
83 24
84 17
91 33
92 6
97 33

output:

7348

result:

ok single line: '7348'

Test #9:

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

input:

12 29 5 1
4 26
5 18
15 15
27 26
31 12
40 0
46 19
67 4
68 2
77 1
83 12
89 10

output:

2134

result:

ok single line: '2134'

Test #10:

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

input:

18 99 5 1
0 10
4 5
9 9
15 0
37 16
38 7
39 5
43 2
53 12
57 18
61 1
64 5
70 12
74 13
78 16
86 19
89 3
99 15

output:

4586

result:

ok single line: '4586'

Test #11:

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

input:

18 60 1 4
0 12
4 37
9 5
14 52
15 54
31 31
34 34
43 36
49 44
59 53
60 18
67 23
70 12
76 15
83 53
96 41
99 52
100 45

output:

4745

result:

ok single line: '4745'

Test #12:

score: -100
Time Limit Exceeded

input:

10000 100000 9990 1
10 722
11 42
30 116
35 438
47 690
49 369
72 234
94 243
101 34
133 884
135 571
143 365
150 829
185 549
186 361
191 698
192 111
194 41
223 249
227 440
232 180
264 679
265 341
273 345
276 700
279 898
293 300
300 878
302 47
313 203
314 105
336 859
337 533
346 163
366 400
370 509
381 ...

output:


result: