我们观察到，整个行为一定能被拆分为全买和全卖。
略微思考一下就可以证明这个定理。倘若先部分买再部分买，再全卖，显然不是优的。因为我们总可以找到更优的部分，使得全买再全卖更优；同理，部分卖再部分卖也一定不会更优。这是因为，券是必须按比例卖出的。 于是，我们就把整个决策拆分为很多个全买和全卖交替出现的点，然后对这些点进行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;
}