QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#398769#2338. Beautiful BridgesBIXIANWA 43ms786836kbC++141.4kb2024-04-25 18:03:442024-04-25 18:03:49

Judging History

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

  • [2024-04-25 18:03:49]
  • 评测
  • 测评结果:WA
  • 用时:43ms
  • 内存:786836kb
  • [2024-04-25 18:03:44]
  • 提交

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[10001][10001];
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][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: 31ms
memory: 785388kb

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: -100
Wrong Answer
time: 43ms
memory: 786836kb

input:

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

output:

4557430888798830399

result:

wrong answer 1st lines differ - expected: 'impossible', found: '4557430888798830399'