QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#507489#2338. Beautiful BridgesflyingWA 1ms3964kbC++14773b2024-08-06 18:18:542024-08-06 18:18:54

Judging History

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

  • [2024-08-06 18:18:54]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3964kb
  • [2024-08-06 18:18:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e4+5;

int dp[N], x[N], y[N], n, h;
bool can[N][N];

int dist(int x1,int y1,int x2,int y2)
{
	return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
}

bool check(int l,int r)
{
	int lim=2*h-(x[r]-x[l]);
	for(int i=l;i<=r;i++)
		if(y[i]*2>lim && dist(x[i]*2,y[i]*2,x[l]+x[r],lim)>(x[r]-x[l])*(x[r]-x[l]))
			return false;
	return true;
}

signed main()
{
	int a,b;
	cin >> n >> h >> a >> b;
	for(int i=1;i<=n;i++)
		scanf("%lld %lld",&x[i],&y[i]);

	memset(dp,0x3f,sizeof(dp));
	dp[1]=a*(h-y[1]);
	for(int i=2;i<=n;i++)
		for(int j=i-1;j>=1;j--)
			if(check(j,i))
				dp[i]=min(dp[i],dp[j]+a*(h-y[i])+b*(x[i]-x[j])*(x[i]-x[j]));
	printf("%lld\n",dp[n]);
	return 0;
}

詳細信息

Test #1:

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

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

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'