分类： 算法

我们观察到，整个行为一定能被拆分为全买和全卖。
略微思考一下就可以证明这个定理。倘若先部分买再部分买，再全卖，显然不是优的。因为我们总可以找到更优的部分，使得全买再全卖更优；同理，部分卖再部分卖也一定不会更优。这是因为，券是必须按比例卖出的。 于是，我们就把整个决策拆分为很多个全买和全卖交替出现的点，然后对这些点进行DP。
我们不妨记\(f_{i}\)表示第i个点为止最多的钱数。倘若第i天花了x来购买A，那么购买的数量是x/A，那么购买了B的数量是x/(A*Rate)，花费的钱是xB/(A*Rate)。可以解得：
$$x=\frac{A*Rate*f_i}{RateA+B}$$
也就是说，购买的A和B券的数量分别是：
$$\frac{Rate*f_i}{RateA+B},\frac{f_i}{RateA+B}$$
那么，我们从j转移到i的方程是：
$$f_j=Max(\frac{A_i*Rate_j*f_j}{Rate_jA_j+B_j}+\frac{B_i*f_j}{Rate_jA_j+B_j})$$
我们考虑这个转移式要如何优化。 我们尝试对这个式子使用斜率优化。然而一个致命的问题是，斜率优化要求我们需要将方程中i的部分和j的部分独立地放在x,y,k,b中，这使得我们设\(f_j=y\)的计划破产了。 我们不妨设：
$$x=\frac{Rate_i*f_i}{Rate_iA_i+B_i},y=\frac{f_i}{Rate_iA_i+B_i}$$
那么我们可以得到： $$f_i=A_ix_j+B_iy_j$$
那么，当前点之前的所有点构成的就是平面上的一些点，然后我们要用这条直线去切这些点，找到截距最大的那个。
通过这个斜率优化，我们把问题如下转换：我们有一个仅包含第一象限的平面，有\(10^5\)个操作，每个操作可能是加入一个点，或查询「经过任意一点的给定斜率的直线的最大截距」。 看起来这似乎需要可持久化凸包或者之类的复杂操作。但仔细观察我们发现这是一个可离线的操作。
因此，我们对时间分治，然后左半部分对x坐标排序——这是为了维护凸包；对右半部分按照斜率从大往小排序。那么对于新加进来的每一个直线，都只有可能找到凸包的下一个点。用单调栈即可。 围凸壳的复杂度是O(n)的，因此可以暴力重构。然后可以一边分治一边排序。 复杂度O(nlogn)
注意：要判一下分母不能等于极小数，否则可能会挂。

略微思考一下就可以证明这个定理。倘若先部分买再部分买，再全卖，显然不是优的。因为我们总可以找到更优的部分，使得全买再全卖更优；同理，部分卖再部分卖也一定不会更优。这是因为，券是必须按比例卖出的。 于是，我们就把整个决策拆分为很多个全买和全卖交替出现的点，然后对这些点进行DP。 我们不妨记\(f_{i}\)表示第i个点为止最多的钱数。倘若第i天花了x来购买A，那么购买的数量是x/A，那么购买了B的数量是x/(A*Rate)，花费的钱是xB/(A*Rate)。可以解得： $$x=\frac{A*Rate*f_i}{RateA+B}$$ 也就是说，购买的A和B券的数量分别是： $$\frac{Rate*f_i}{RateA+B},\frac{f_i}{RateA+B}$$ 那么，我们从j转移到i的方程是： $$f_j=Max(\frac{A_i*Rate_j*f_j}{Rate_jA_j+B_j}+\frac{B_i*f_j}{Rate_jA_j+B_j})$$ 我们考虑这个转移式要如何优化。 我们尝试对这个式子使用斜率优化。然而一个致命的问题是，斜率优化要求我们需要将方程中i的部分和j的部分独立地放在x,y,k,b中，这使得我们设\(f_j=y\)的计划破产了。 我们不妨设： $$x=\frac{Rate_i*f_i}{Rate_iA_i+B_i},y=\frac{f_i}{Rate_iA_i+B_i}$$ 那么我们可以得到： $$f_i=A_ix_j+B_iy_j$$ 那么，当前点之前的所有点构成的就是平面上的一些点，然后我们要用这条直线去切这些点，找到截距最大的那个。 通过这个斜率优化，我们把问题如下转换：我们有一个仅包含第一象限的平面，有\(10^5\)个操作，每个操作可能是加入一个点，或查询「经过任意一点的给定斜率的直线的最大截距」。 看起来这似乎需要可持久化凸包或者之类的复杂操作。但仔细观察我们发现这是一个可离线的操作。 因此，我们对时间分治，然后左半部分对x坐标排序——这是为了维护凸包；对右半部分按照斜率从大往小排序。那么对于新加进来的每一个直线，都只有可能找到凸包的下一个点。用单调栈即可。 围凸壳的复杂度是O(n)的，因此可以暴力重构。然后可以一边分治一边排序。 复杂度O(nlogn) 注意：要判一下分母不能等于极小数，否则可能会挂。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;

const int N=100005;
const double eps=1E-10;
const double INF=1E10;
struct data{
	double a;double b;double r;int id;double x;double y;
}a[N],b[N];
//斜率从大往小排序。 
inline double cmp(const data &A,const data &B){
	return A.a*B.b>B.a*A.b; 
}
int n,st[N],tp=0;double m,f[N];
inline double icpt(int P,double A,double B){
//	printf("icpt:%lf\n",a[P].x*A+a[P].y*B);
	return a[P].x*A+a[P].y*B; 
}
inline double slp(int A,int B){
	if(fabs(a[A].x-a[B].x)<eps){
		return INF;
	}
	return (a[A].y-a[B].y)/(a[A].x-a[B].x);
}
inline void mg(int l,int r){
	int mid=(l+r)>>1;
	int I=l,J=mid+1,tp=l;
	while(I<=mid&&J<=r){
		if(a[I].x<a[J].x){
			b[tp++]=a[I++];
		}else{
			b[tp++]=a[J++];
		}
	}
	while(I<=mid){
		b[tp++]=a[I++];
	}
	while(J<=r){
		b[tp++]=a[J++];
	}
	for(int i=l;i<=r;++i){
		a[i]=b[i];
	}
}
inline void cdq(int l,int r){
	if(l==r){
		f[l]=max(f[l],f[l-1]);
		a[l].y=(double)f[l]/(a[l].r*a[l].a+a[l].b);
		a[l].x=(double)a[l].r*a[l].y;
		return;
	}
	int mid=(l+r)>>1;
	int I=l,J=mid+1;
	for(int i=l;i<=r;++i){
		if(a[i].id<=mid){
			b[I++]=a[i];
		}else{
			b[J++]=a[i];
		}
	}
	for(int i=l;i<=r;++i){
		a[i]=b[i];
	}
	cdq(l,mid);
	tp=0;
	for(int i=l;i<=mid;++i){
		while(tp>1&&slp(st[tp],i)+eps>slp(st[tp-1],st[tp])){
			--tp;
		}
		st[++tp]=i;
	}
//	printf("[%d,%d]\n",l,r);
//	for(int i=1;i<=tp;++i){
//		printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
//	}
	for(int i=mid+1;i<=r;++i){
		while(tp>1&&slp(st[tp],st[tp-1])<=-a[i].a/a[i].b+eps){
			--tp;
		}
		f[a[i].id]=max(f[a[i].id],icpt(st[tp],a[i].a,a[i].b));
//		printf("%d %lf\n",i,a[i].ans); 
	}
	cdq(mid+1,r);
	mg(l,r);
}
void init(){
	scanf("%d%lf",&n,&f[0]);
	for(int i=1;i<=n;++i){
		scanf("%lf%lf%lf",&a[i].a,&a[i].b,&a[i].r);
		a[i].id=i;
	}
	std::sort(a+1,a+1+n,cmp);
	cdq(1,n);
//	for(int i=1;i<=n;++i){
//		printf("%d:%lf,%lf %lf %lf\n",a[i].id,a[i].x,a[i].y,-(double)a[i].a/a[i].b,f[a[i].id]);
//	}
	printf("%.3lf\n",f[n]);
}
int main(){
	init();
	return 0;
}