QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#507484#2338. Beautiful BridgesflyingRE 0ms0kbC++14985b2024-08-06 18:13:522024-08-06 18:13:52

Judging History

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

  • [2024-08-06 18:13:52]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-08-06 18:13:52]
  • 提交

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(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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

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

output:


result: