【模板】李超线段树优化斜率优化 DP。（什么烂名字）
注意到题给条件说每次都可以把 钱 / 金圆券 换完。金券信息是不好存储的，于是我们规定 \(\mathrm{dp}_i\) 表示在第 \(i\) 天最多能赚到多少钱。dp 时枚举上一次把钱换成金券的时间。换金券应该是很好算的，推一下就出来了。
那么有转移 \(\mathrm{dp}_i = \max\{a_ic_j+b_id_j\} = b_i\max\{c_i \frac{a_i}{b_i} + d_j\}\)，其中 \(c, d\) 是第 \(j\) 天换到的两种金券的数量。
用李超树维护斜率优化 DP 即可。
#include <bits/stdc++.h>
#define llong long long
#define N 100005
using namespace std;constexpr double eps = 1e-7;
inline int cmp(double a, double b){if(fabs(a-b) < eps) return 0;return a>b ? 1 : -1;
}int n; double s;
double a[N], b[N], r[N]; int k[N];
double dp[N], tmp[N]; int cnt;struct Seg{double k, b; bool vis;};
#define gety(s,x) (s.k*(x)+s.b)Seg val[N<<2];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((l+r)>>1)
inline void insert(Seg k, int x = 1, int l = 1, int r = cnt){if(!val[x].vis){val[x] = k;return;}Seg s1 = val[x], s2 = k;if(cmp(gety(s1, tmp[mid]), gety(s2, tmp[mid])) < 0) swap(s1, s2);val[x] = s1;if(cmp(gety(s1, tmp[l]), gety(s2, tmp[l])) < 0) insert(s2, ls(x), l, mid );if(cmp(gety(s1, tmp[r]), gety(s2, tmp[r])) < 0) insert(s2, rs(x), mid+1, r);return;
}
inline double query(int pos, int x = 1, int l = 1, int r = cnt){double res = -1e18;if(val[x].vis) res = gety(val[x], tmp[pos]);if(l == r) return res;if(pos <= mid) res = max(res, query(pos, ls(x), l, mid ));else res = max(res, query(pos, rs(x), mid+1, r));return res;
}int main(){scanf("%d %lf", &n, &s);for(int i = 1; i <= n; ++i){scanf("%lf %lf %lf", &a[i], &b[i], &r[i]);tmp[++cnt] = a[i]/b[i];}sort(tmp+1, tmp+cnt+1);cnt = unique(tmp+1, tmp+cnt+1, [&](double a, double b){return fabs(a-b)<eps;})-tmp-1;for(int i = 1; i <= n; ++i)k[i] = upper_bound(tmp+1, tmp+cnt+1, a[i]/b[i]+eps)-tmp-1;dp[0] = s;for(int i = 1; i <= n; ++i){dp[i] = max(dp[i-1], b[i]*query(k[i]));insert((Seg){(dp[i]*r[i])/(a[i]*r[i]+b[i]), dp[i]/(a[i]*r[i]+b[i]), true});}printf("%.7f", dp[n]);return 0;
}