wa*10 求助
查看原帖
wa*10 求助
66964
heyuguo楼主2024/8/20 10:19
#include<bits/stdc++.h>
using namespace std;
long long n,A,v[2005],x[2005],w[2005],ans,tot;
struct node
{
	long double t;//时间点 
	long long e;//价值的变化量 
}a[200005];
bool cmp(node a,node b)
{
	if(fabs(a.t-b.t)>1e-7)
		return a.t<b.t;
	else
		return a.e>b.e;
}
int main()
{
	cin>>n>>A;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>x[i]>>v[i];
	}
	for(int i=1;i<=n;i++)
	{
		long long cnt=w[i];
		for(int j=1;j<=n;j++)
		{
			if(j==i)continue;
			if(v[i]==v[j])
			{
				if((x[j]-x[i])<=A&&(x[j]-x[i])>=0)
					cnt+=w[j];
			}
			else
			{
				long double t=(x[j]-x[i])*1.0/(v[i]-v[j]),ta=t+A*1.0/(v[i]-v[j]);
				if(v[i]>v[j])
				{
					a[++tot]={t,w[j]};
					a[++tot]={ta,-w[j]};
				}
				else
				{
					a[++tot]={ta,w[j]};
					a[++tot]={t,-w[j]};
				}
			}
		}
		sort(a+1,a+tot+1,cmp);
		ans=max(cnt,ans);
//		for(int i=1;i<=tot;i++)
//		{
//			cout<<a[i].t<<' '<<a[i].e<<'\n';
//		}
//		cout<<'\n';
		for(int j=1;j<=tot;j++)
		{
			cnt+=a[j].e;
			if(a[j].t>=-1e-7)
				ans=max(ans,cnt);
		}
		tot=0;
	}
	cout<<ans<<'\n';
	return 0;
}
2024/8/20 10:19
加载中...