求助精度(wa#5,7)
查看原帖
求助精度(wa#5,7)
553501
可爱的小棉羊楼主2024/12/11 16:28
#include<bits/stdc++.h>
using namespace std;
const long double eps=1e-15;
struct node{
	long double x,y;
};
struct Node{
	node dot;
	int id;
}v[100005];
long double f[100005],a[100005],b[100005],R[100005],T[100005],s;
int n,cnt;
bool cmp(Node x,Node y){
	return x.id<y.id;
}
bool cmp2(Node x,Node y){
	return x.dot.x<y.dot.x;
}
bool cmp3(Node x,Node y){
	return (-a[x.id]/b[x.id])>(-a[y.id]/b[y.id]);
}
double getk(node x,node y){
	if(abs(x.x-y.x)<=eps){
		if(x.y<y.y)return 1e12;
		return -1e12;
	}
	return (y.y-x.y)/(y.x-x.x);
}
node st[100005];

void cdq(int l,int r){
	if(l==r){
		v[l].dot={R[l]/T[l]*f[l],f[l]/T[l]};
		return;
	}
	
	int mid=(l+r)>>1,L=1;
	cdq(l,mid);
	f[mid+1]=max(f[mid],f[mid+1]);
	sort(v+l,v+mid+1,cmp2);
	sort(v+mid+1,v+r+1,cmp3);
	cnt=0;
	st[++cnt]=v[l].dot;
	for(int i=l+1;i<=mid;i++){
		while(cnt>=2&&getk(st[cnt-1],v[i].dot)-getk(st[cnt-1],st[cnt])>=eps)cnt--;
		st[++cnt]=v[i].dot;
	}
	for(int i=mid+1;i<=r;i++){
		long double K=-a[v[i].id]/b[v[i].id];
		while(L<cnt&&getk(st[L],st[L+1])>K)L++;
		f[v[i].id]=max(f[v[i].id],st[L].x*a[v[i].id]+st[L].y*b[v[i].id]);
	}
	sort(v+mid+1,v+r+1,cmp);
	cdq(mid+1,r);
	sort(v+l,v+r+1,cmp);
}
int main(){
	cin>>n>>s;
	f[1]=s;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i]>>R[i];
		T[i]=a[i]*R[i]+b[i];
	}
	for(int i=1;i<=n;i++)v[i]={{0,0},i};
	cdq(1,n);
	cout<<f[n]<<"\n";
}
2024/12/11 16:28
加载中...