§ Description

Link.

一共 $n$ 天，每天可以卖出或者买入两种股票 $A$ 和 $B$。这两种股票在第 $i$ 天的价值为 $A_i$ 和 $B_i$。

每天可以花所有的现金买入股票，这些股票中 $A$ 股与 $B$ 股的数量比为 $rate_i$。每天也可以把所有的股票以当天的价值卖出，获得现金。已知接下来 $n$ 天的 $A_i,B_i,rate_i$，求出 $n$ 天后能够获得的最大价值。

§ Solution

设 $f(i)$ 为第 $i$ 天的最大钱数，$g_{1}(i)$ 为 A 券的第 $i$ 天能换的数量，$g_{2}(i)$ 则为 B 券。

转移可以解方程得：

两个 $g$ 都没啥问题，主要来看 $f(i)$。提一下可得：

斜率优化的形式，但斜率并无单调性。那个 $f(i-1)$ 可以最后来线性做，所以可以先不管。然后就是 li-chao tree 的板子。

#include<bits/stdc++.h>
std::vector<double> pri;
int n,nodes[400010];
double g[5][100010],f[100010],a[100010],b[100010],rate[100010],slp[100010];
double _f(int i,int j){return pri[i-1]*g[1][j]+g[2][j];}
void ins(int l,int r,int x,int i)
{
	if(l^r)
	{
		int mid=(l+r)>>1;
		if(_f(mid,i)>_f(mid,nodes[x]))	std::swap(nodes[x],i);
		if(_f(l,i)>_f(l,nodes[x]))	ins(l,mid,x<<1,i);
		else	ins(mid+1,r,x<<1|1,i);
	}
	else if(_f(l,i)>_f(l,nodes[x]))	nodes[x]=i;
}
double find(int l,int r,int x,int i)
{
	if(l^r)
	{
		int mid=(l+r)>>1;
		if(mid>=i)	return std::max(find(l,mid,x<<1,i),_f(i,nodes[x]));
		else	return std::max(find(mid+1,r,x<<1|1,i),_f(i,nodes[x]));
	}
	else	return _f(i,nodes[x]);
}
#define All(x) (x).begin(),(x).end()
int main()
{
	double pref=0,nowf=0;
	scanf("%d %lf",&n,&nowf);
	pref=nowf;
	for(int i=1;i<=n;++i)
	{
		scanf("%lf %lf %lf",&a[i],&b[i],&rate[i]);
		slp[i]=a[i]/b[i];
		pri.emplace_back(slp[i]);
	}
	std::sort(All(pri));
	for(int i=1;i<=n;++i)
	{
		nowf=std::max(pref,b[i]*find(1,n,1,std::lower_bound(All(pri),slp[i])-pri.begin()+1));
		g[1][i]=nowf*rate[i]/(a[i]*rate[i]+b[i]);
		g[2][i]=nowf/(a[i]*rate[i]+b[i]);
		ins(1,n,1,i);
		pref=nowf;
	}
	printf("%.3f\n",nowf);
	return 0;
}