QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#398783#2338. Beautiful BridgesBIXIANTL 52ms787184kbC++141.5kb2024-04-25 18:09:232024-04-25 18:09:29

Judging History

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

  • [2024-04-25 18:09:29]
  • 评测
  • 测评结果:TL
  • 用时:52ms
  • 内存:787184kb
  • [2024-04-25 18:09:23]
  • 提交

answer

#include<iostream>
#include<algorithm>
#include<cstring>
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]!=qw[10001][10001])
				{
					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 max1 = 0,x,fr;
	for (int i = 1; i <= 100000; i++)
		f[i] = -1;
	for (int i = 1; i <= n; i++)
	{
		cin >> x;
		cin >> f[x];
		ans++;
		s[ans][0] = x;
		if (f[x] > max1)
			max1 = f[x];
	}
	memset(qw, 0x3f3f, sizeof(qw));
	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: 27ms
memory: 786440kb

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: 36ms
memory: 785856kb

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: 43ms
memory: 787084kb

input:

2 1 1 1
0 0
2 0

output:

6

result:

ok single line: '6'

Test #4:

score: 0
Accepted
time: 12ms
memory: 785948kb

input:

2 1 1 1
0 0
3 0

output:

impossible

result:

ok single line: 'impossible'

Test #5:

score: 0
Accepted
time: 23ms
memory: 785460kb

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: 23ms
memory: 786428kb

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: 24ms
memory: 786992kb

input:

2 100000 10000 10000
0 0
100000 0

output:

100002000000000

result:

ok single line: '100002000000000'

Test #8:

score: 0
Accepted
time: 44ms
memory: 787180kb

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: 11ms
memory: 785888kb

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: 52ms
memory: 786424kb

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: 23ms
memory: 787184kb

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: