QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#398794#2338. Beautiful BridgesBIXIANTL 2ms6272kbC++141.5kb2024-04-25 18:14:522024-04-25 18:14:53

Judging History

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

  • [2024-04-25 18:14:53]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:6272kb
  • [2024-04-25 18:14:52]
  • 提交

answer

#include<iostream>
#include<algorithm>
using namespace std;
int f[100001];
long long n, h, a, d,ans,w;
long long s[100001][2];
long long qw[10002][10002];
bool df(int a, int b)
{
	double midx = ((double)a + (double)b) / 2;
	double midy = h - ((double)b - (double)a) / 2;
	if (midy < f[a] || midy < f[b])
	{
		return 0;
	}
	double r = ((double)b - (double)a) / 2;
	for (int i = a; i <= b; i++)
	{
		if (f[i]>=0)
		{
			if ((f[i]>=midy)&&((midx - (double)i) * (midx - (double)i) + (midy - (double)f[i]) * (midy - (double)f[i]))>(r*r))
				return 0;
		}
	}
	return 1;
}
int vv = 0;
long long min1 = -1;
void dfs(int qe)
{
	for (int i = 2; i <= ans; i++)
	{
		for (int j = 1; j <= i-1; j++)
		{
			for (int u = 1; u < i; u++)
			{
				if ((df(s[u][0], s[i][0]))&& qw[j - 1][u])
				{
					if (!qw[j][i])
						qw[j][i] = qw[j - 1][u] + d * ((s[i][0] - s[u][0]) * (s[i][0] - s[u][0])) + a * (h - f[s[i][0]]);
					else
							qw[j][i] = min(qw[j][i], qw[j - 1][u] + d * ((s[i][0] - s[u][0]) * (s[i][0] - s[u][0])) + a * (h - f[s[i][0]]));
					if (i == ans)
					{
						if (min1 > qw[j][i]||min1==-1)
							min1 = qw[j][i];
						vv = 1;
					}
				}
			}
		}
	}
}
int main()
{
	cin >> n >> h >> a >> d;
	int x,fr;
	ans = n;
	for (int i = 1; i <= 100000; i++)
		f[i] = -1;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d",&x);
		scanf("%d",&f[x]);
		s[i][0] = x;
	}
	qw[0][1] = a*(h-f[s[1][0]]);
	dfs(1);
	if (!vv)
		cout << "impossible";
	if(vv)
		cout << min1 << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5848kb

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

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

input:

2 1 1 1
0 0
2 0

output:

6

result:

ok single line: '6'

Test #4:

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

input:

2 1 1 1
0 0
3 0

output:

impossible

result:

ok single line: 'impossible'

Test #5:

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

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

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

input:

2 100000 10000 10000
0 0
100000 0

output:

100002000000000

result:

ok single line: '100002000000000'

Test #8:

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

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

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

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

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: