QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398752#2338. Beautiful BridgesBIXIANTL 2ms3704kbC++142.0kb2024-04-25 17:45:252024-04-25 17:45:26

Judging History

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

  • [2024-04-25 17:45:26]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3704kb
  • [2024-04-25 17:45:25]
  • 提交

answer

#include<iostream>
using namespace std;
int f[100001];
long long n, h, a, d,ans,w;
long long s[100001][2];
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 = 99999999999999999;
void dfs(int i)
{
	for (int j = i + 1; j <= ans; j++)
	{
		if ((df(s[i][0], s[j][0])))
		{
			s[i][1] = j;
			w += d * ((s[j][0] - s[i][0]) * (s[j][0] - s[i][0]))+a * (h - f[s[j][0]]);
			if (j == ans)
			{
				if (min1 > w)
					min1 = w;
				vv = 1;
				w -= d * ((s[j][0] - s[i][0]) * (s[j][0] - s[i][0])) + a * (h - f[s[j][0]]);
				return;
			}
			dfs(j);
			w -= d * ((s[j][0] - s[i][0]) * (s[j][0] - s[i][0]))+a * (h - f[s[j][0]]);
		}
	}
}
int main()
{
	cin >> n >> h >> a >> d;
	int max1 = 0,x,fr;
	for (int i = 1; i <= 99; 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];
	}
	w += a * (h - f[s[1][0]]);
	dfs(1);
	if (!vv)
		cout << "impossible";
	if(vv)
	{
		cout << min1 << endl;
		/*while (1)
		{
			int yy = 1;
			bool v = 1;
			while (yy != ans && s[yy][1] != ans)
			{
				if (df(s[yy][0], s[s[s[yy][1]][1]][0]))
				{
					int qw = h - f[s[s[yy][1]][0]];
					int qe = (s[s[s[yy][1]][1]][0] - s[yy][0]) * (s[s[s[yy][1]][1]][0] - s[yy][0]);
					int qe1 = (s[s[s[yy][1]][1]][0] - s[s[yy][1]][0]) * (s[s[s[yy][1]][1]][0] - s[s[yy][1]][0]);
					int qe2 = (s[s[yy][1]][0] - s[yy][0]) * ((s[s[yy][1]][0] - s[yy][0]));
					if (a * qw > d * (qe - qe1 - qe2))
					{
						v = 0;
						s[yy][1] = s[s[yy][1]][1];
						w -= a * qw - d * (qe - qe1 - qe2);
					}
				}
				yy = s[yy][1];
			}
			if (v)
				break;
		}
		cout << w;*/
	}
}

詳細信息

Test #1:

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

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

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

input:

2 1 1 1
0 0
2 0

output:

6

result:

ok single line: '6'

Test #4:

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

input:

2 1 1 1
0 0
3 0

output:

impossible

result:

ok single line: 'impossible'

Test #5:

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

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

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

input:

2 100000 10000 10000
0 0
100000 0

output:

100002000000000

result:

ok single line: '100002000000000'

Test #8:

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

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

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

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

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: