首先有一个显然的贪心，每次操作都要做到底，为了最优不会出现只卖一部分或者只买一部分的操作
所以设 $f[i]$ 表示前 $i$ 天得到的最大价值，那么对于每一个 $i$，枚举所有 $j<i$，意思就是第 $j$ 天全部买入，第 $i$ 天全部卖出
显然如果知道 $f[j]$，那么就知道第 $j$ 天买入多少
设 $A$ 买了 $X$， $B$ 买了 $Y$，那么 $f[i]=a[i]*X+b[i]*Y$
因为 $X,Y$ 只和 $j$ 有关，显然可以斜率优化
具体就是 $-a[i]*X+f[i]=b[i]*Y$，同除一个 $b[i]$，变成 $-a[i]/b[i]*X+f[i]/b[i]=Y$
那么 $k=-a[i]/b[i],x=X,b=f[i]/b[i],y=Y$
自己推一下，容易得出 $X_i=f[i]*r[i]/(a[i]*r[i]+b[i]),Y_i=f[i]/(a[i]*r[i]+b[i])$
然后因为 $k,x$ 都不单调，所以要用 $CDQ$ 搞
先按斜率排序，然后 $CQD$ 分治之前按下标拆成两部分，这个具体还是看代码吧...
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
typedef double db;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }
return x*f;
}
const int N=2e5+,INF=1e9+;
const db eps=1e-;
int n,S;
db f[N];
struct dat{
db k,x,y,a,b,r;
int id;
inline bool operator < (const dat &tmp) const {
return k<tmp.k;
}
}T[N],tmp[N];
inline db slope(int i,int j)//求斜率维护凸包
{
if(fabs(T[i].x-T[j].x)<=eps) return T[i].y>T[j].y ? INF : -INF;
return (T[i].y-T[j].y)/(T[i].x-T[j].x);
}
inline db Cross(db xa,db ya,db xb,db yb) { return xa*yb-xb*ya; }//用叉积维护凸包会更快
inline void merge(int l,int r,int mid)//按x归并排序
{
int pl=l,pr=mid+;
for(int p=l;p<=r;p++)
{
if(pl<=mid&& (pr>r||T[pl].x<T[pr].x/*+eps*/) ) tmp[p]=T[pl++];
else tmp[p]=T[pr++];
}
for(int p=l;p<=r;p++) T[p]=tmp[p];
}
int Q[N];//栈，维护凸包
void CDQ(int l,int r)
{
if(l==r)//到了最底下，此时f[l]已经被所有f[j](j<l)更新完毕
{
f[l]=max(f[l],f[l-]);//这一天可以不操作
T[l].y=f[l]/(T[l].a*T[l].r+T[l].b),T[l].x=T[l].y*T[l].r;
//更新f[l]完才求X[l],Y[l]
return;
}
int mid=l+r>>,pl=l,pr=mid+,top=;
for(int p=l;p<=r;p++)//按下标分开
{
if(T[p].id<=mid) tmp[pl++]=T[p];
else tmp[pr++]=T[p];
}
for(int p=l;p<=r;p++) T[p]=tmp[p];
CDQ(l,mid); Q[]=;//先处理左边
for(int i=l;i<=mid;i++)//此时左边全部更新完毕，可以维护左边构成的凸包了
//注意此时左边的T[i].x是有序的,因为每次CDQ结束都会merge
{
while( top> &&
Cross(T[i].x-T[Q[top-]].x,T[i].y-T[Q[top-]].y,T[Q[top]].x-T[Q[top-]].x,T[Q[top]].y-T[Q[top-]].y)<= ) top--;
Q[++top]=i;
}
for(int i=mid+;i<=r;i++)//用左边构成的凸包更新右边,此时右边的斜率是有序的
{
while( top> && /*T[i].k>=slope(Q[top-1],Q[top])+eps*/ //注释的内容和下一行是等价的,注意eps
Cross(,T[i].k,T[Q[top]].x-T[Q[top-]].x,T[Q[top]].y-T[Q[top-]].y)<= ) top--;
int j=Q[top]; f[T[i].id]=max(f[T[i].id],T[j].x*T[i].a+T[j].y*T[i].b);//更新
}
CDQ(mid+,r); merge(l,r,mid);//处理右边后按x排序
}
int main()
{
n=read(); f[]=read();
for(int i=;i<=n;i++)
{
scanf("%lf%lf%lf",&T[i].a,&T[i].b,&T[i].r);
T[i].k=-T[i].a/T[i].b; T[i].id=i;//初始化
}
sort(T+,T+n+); CDQ(,n);//先按k排序再CDQ
printf("%.3lf",f[n]);
return ;
}