TLE 65 分求条
查看原帖
TLE 65 分求条
752953
sLMxf楼主2024/11/27 14:03
#include<bits/stdc++.h>
#define file(name) freopen(name".in","r",stdin);freopen(name".out","w",stdout);
using namespace std;
int ls[114514*2],tot=0;
int p[114514*2],t[114514*2],x[114514*2],y[114514*2];
long double dp[2][55][45][2],ans[114514*2];
unordered_map<int,int>dy,di;
unordered_map<int,bool>jy;
void lsh()
{
	sort(ls+1,ls+tot+1);
	tot=unique(ls+1,ls+tot+1)-ls-1;
	for(int i=1;i<=tot;i++) dy[ls[i]]=i,di[i]=ls[i];
}
int Y,n;
double dfs(int c,double v,double T)
{
	if(c==n||p[c+1]>Y) return min(T+(Y-p[c])/v,T+t[c]+(Y-p[c])/v/x[c]);
	return min(dfs(c+1,v*x[c],T+t[c]+(p[c+1]-p[c])/v/x[c]),dfs(c+1,v,T+(p[c+1]-p[c])/v));
}
signed main()
{
	int q,maxj=0,maxk=0,miao,TnT=0;
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>p[i]>>t[i]>>x[i],ls[++tot]=p[i],jy[p[i]]=1;
	for(int i=1;i<=q;i++) cin>>y[i],ls[++tot]=y[i];
	lsh();
	for(int i=1;i<=tot;i++) ans[i]=INT_MAX;
	for(int i=0;i<2;i++)
		for(int j=0;j<55;j++)
			for(int k=0;k<45;k++)
				for(int l=0;l<2;l++)
					dp[i][j][k][l]=INT_MAX;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			dp[i][0][0][j]=0;
	p[0]=t[0]=0,x[0]=1;
	for(int i=1;i<=tot;i++)
	{
		double sudo=1;
		int two=0,thr=0;
		if(jy[di[i]]==1) TnT++;
		if(jy[di[i]]==1)
		{
			if(x[TnT]%2==0) two=x[TnT]/2;
			if(x[TnT]%3==0) thr=x[TnT]/3;
			maxj+=two,maxk+=thr;
			for(int j=0;j<=min(maxj,31);j++)
			{
				if(j) sudo*=2;
				miao=sudo;
				for(int k=0;k<=min(maxk,20);k++)
				{
					if(k) sudo*=3;
					int S=di[i]-di[i-1];
					sudo/=(two==2?4:(two==1?2:1))*(thr==1?3:1);
					
					dp[1][j][k][0]=min(dp[0][j][k][1],dp[0][j][k][0])+S*1.0/(sudo*(two==2?4:(two==1?2:1))*(thr==1?3:1));
					if(j-two>=0&&k>=thr) dp[1][j][k][1]=min(dp[0][j-two][k-thr][1],dp[0][j-two][k-thr][0])+S*1.0/sudo+t[TnT];
					else dp[1][j][k][1]=INT_MAX;
					ans[i]=min(ans[i],min(dp[1][j][k][1]-t[TnT],dp[1][j][k][0]));
					
					sudo*=(two==2?4:(two==1?2:1))*(thr==1?3:1);
				}
				sudo=miao;
			}
		}
		else
		{
			for(int j=0;j<=min(maxj,31);j++)
			{
				if(j) sudo*=2;
				miao=sudo;
				for(int k=0;k<=min(maxk,20);k++)
				{
					if(k) sudo*=3;
					dp[1][j][k][0]=dp[1][j][k][1]=min(dp[0][j][k][1],dp[0][j][k][0])+(di[i]-di[i-1])*1.0/sudo;
					ans[i]=min(ans[i],min(dp[1][j][k][1],dp[1][j][k][0]));
				}
				sudo=miao;
			}
		}
		for(int j=0;j<=min(maxj,31);j++)
				for(int k=0;k<=min(maxk,20);k++)
				{
					dp[0][j][k][0]=dp[1][j][k][0],dp[0][j][k][1]=dp[1][j][k][1];
				}
	}
	for(int i=1;i<=q;i++) printf("%.9Lf\n",ans[dy[y[i]]]);
	return 0;
}

rt

2024/11/27 14:03
加载中...