QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#398842#2338. Beautiful BridgesBIXIANTL 1ms5812kbC++141.4kb2024-04-25 19:01:122024-04-25 19:01:14

Judging History

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

  • [2024-04-25 19:01:14]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:5812kb
  • [2024-04-25 19:01:12]
  • 提交

answer

#include<iostream>
#include<algorithm>
using namespace std;
int f[100001];
long long n, h, a, d,ans;
long long s[100001][2];
long long qw[10002],qe[10002];
bool df(int a, int b)
{
	long long midy = 10*h - 5*(b - a);
	if (midy < 10*f[a] || midy < 10*f[b])
		return 0;
	long long midx = (a + b)*5;
	long long r = (b -a)*5;
	r *= r;
	for (int i = a; i <= b; i++)
	{
		if (f[i]>=0)
		{
			if ((10*f[i]>=midy)&&((midx - 10*i) * (midx - 10*i) + (midy - 10*f[i]) * (midy - 10*f[i]))>r)
				return 0;
		}
	}
	return 1;
}
int vv = 0;
long long min1 = -1;
void dfs()
{
	for (int i = 2; i <= ans; i++)
	{
		for (int u = i-1; u>=1; u--)
		{
			if (qw[u]&&(df(s[u][0], s[i][0])))
			{
				if (!qw[i])
				{
					qw[i] = qw[u] + d * ((s[i][0] - s[u][0]) * (s[i][0] - s[u][0])) + s[i][1];
					
				}
				else
				{
					qw[i] = min(qw[i], qw[u] + d * ((s[i][0] - s[u][0]) * (s[i][0] - s[u][0])) + s[i][1]);
					
				}
				if (i == ans)
				{
					if (min1 > qw[i]||min1==-1)
						min1 = qw[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;
		s[i][1] = a * (h - f[s[i][0]]);
	}
	qw[1] = s[1][1];
	
	dfs();
	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: 1ms
memory: 4000kb

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: 1ms
memory: 4132kb

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

input:

2 1 1 1
0 0
2 0

output:

6

result:

ok single line: '6'

Test #4:

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

input:

2 1 1 1
0 0
3 0

output:

impossible

result:

ok single line: 'impossible'

Test #5:

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

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: 1ms
memory: 5812kb

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: 1ms
memory: 3976kb

input:

2 100000 10000 10000
0 0
100000 0

output:

100002000000000

result:

ok single line: '100002000000000'

Test #8:

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

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: 1ms
memory: 4000kb

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: 1ms
memory: 3980kb

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: 1ms
memory: 3996kb

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: