QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#507485#2338. Beautiful BridgesflyingWA 0ms3772kbC++14995b2024-08-06 18:14:442024-08-06 18:14:45

Judging History

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

  • [2024-08-06 18:14:45]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3772kb
  • [2024-08-06 18:14:44]
  • 提交

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]);

	int r=1;
	for(int i=1;i<=n;i++)
	{
		while(r+1<=n && check(i,r+1))
			r++;

		if(r==i)
		{
			printf("impossible\n");
			return 0;
		}

		for(int j=i+1;j<=r;j++)
			can[i][j]=true;
	}

	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(can[j][i])
				dp[i]=min(dp[i],dp[j]+a*(h-y[i])+b*(x[i]-x[j])*(x[i]-x[j]));
			else
				break;
	printf("%lld\n",dp[n]);
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3772kb

input:

5 60 18 2
0 0
20 20
30 10
50 30
70 20

output:

impossible

result:

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