设f[i]是第i天能获得的最大钱数,那么
f[i]=max{在第j天用f[j]的钱买,然后在第i天卖得到的钱,f[i-1]}
然后解一解方程什么的,设$x[j]=\frac{F[j]}{A[j]*Rate[j]+B[j]}$,$y[j]=Rate[j]*x[j]$的话,就能得到$f[i]=max\{y[j]*A[i]+x[j]*B[i],f[i-1]\}$
然后再推一波斜率优化的式子,就可以得到,当j1比j2优时,$\frac{y[j1]-y[j2]}{x[j1]-x[j2]}<-\frac{B[i]}{A[i]}$
然而$-\frac{B[i]}{A[i]}$这玩意并不单调,所以需要用splay或者cdq分治维护一个斜率递减的凸包,来查询满足上式的斜率最大的那个点。
然而懒得写splay了,所以用cdq分治来做(wa了几发以后才发现还不如去写splay呢写splay就不只是wa了)
我们来分治对所有点的询问。当然需要按照i从小到大来做。
然后在做一个区间的时候,我是想用它的左子区间(保证这些的值已经求完了)去更新右子区间的值。
也就是说,需要先做左子区间,然后做当前区间,最后再做右子区间(原理和寻找宝藏是一样的)
做的时候,左边按x值排序,右边按$-\frac{B[i]}{A[i]}$排序,然后给左半边用栈维护一个凸包,再用右半边的去扫,更新结果就行了。
(别忘了f[i]可以等于f[i-1],具体做法是在l=r的时候更新一下)
(常数好像写得很大..不管了.....)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<ctime>
#define LL long long
using namespace std;
const int maxn=; LL rd(){
LL x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,stk[maxn],arr[maxn],tmp[maxn];
double f[maxn],A[maxn],B[maxn],R[maxn]; inline double gety(int i){return R[i]*f[i]/(A[i]*R[i]+B[i]);}
inline double getx(int i){return f[i]/(A[i]*R[i]+B[i]);}
inline double gett(int i){return -B[i]/A[i];}
inline double getk(int i,int j){
double dx=getx(i)-getx(j);if(fabs(dx)<=1e-) dx=1e-;
return (gety(i)-gety(j))/dx;
}
inline bool cmpl(int a,int b){return getx(a)<getx(b);}
inline bool cmpr(int a,int b){return gett(a)<gett(b);} void cdq(int l,int r){
if(l>=r){f[arr[l]]=max(f[arr[l]],f[arr[l]-]);return;}
int m=l+r>>,t=;
cdq(l,m);sort(arr+l,arr+m+,cmpl);
memcpy(tmp+m+,arr+m+,*(r-m));sort(arr+m+,arr+r+,cmpr);
for(int p=l;p<=m;p++){
while(t>=&&getk(stk[t],stk[t-])<getk(stk[t],arr[p])) t--;
stk[++t]=arr[p];
}for(int q=m+;q<=r;q++){
while(t>=&&getk(stk[t],stk[t-])<gett(arr[q])) t--;
int j=stk[t],i=arr[q];
f[i]=max(f[i],gety(j)*A[i]+getx(j)*B[i]);
}
memcpy(arr+m+,tmp+m+,*(r-m));cdq(m+,r);
} int main(){
//freopen("testdata.in","r",stdin);
//freopen(".out","w",stdout);
int i,j,k;
N=rd(),f[]=rd();
for(i=;i<=N;i++){
scanf("%lf%lf%lf",&A[i],&B[i],&R[i]);
arr[i]=i;
}cdq(,N);
double ans=;
for(i=;i<=N;i++){
ans=max(ans,f[i]);
}printf("%.3lf\n",ans);
return ;
}