首先每次买卖一定是在某天 $k$ 以当时的最大收入买入，再到第 $i$ 天卖出，那么易得方程：
$$f_i = \max \{\frac{A_iRate_kf_k}{A_kRate_k + B_k} + \frac{B_if_k}{A_kRate_k + B_k}\}$$
再令
$$\left\{\begin{aligned} x_k = \frac{Rate_kf_k}{A_kRate_k + B_k} \\ y_k = \frac{f_k}{A_kRate_k + B_k}\end{aligned}\right.$$
则有
$$\begin{aligned} f_i &= \max \{A_ix_k + B_iy_k\} \\ y_k &= - \frac{A_i}{B_i}x_k + \frac{f_i}{B_i} \end{aligned}$$
那么现在需要找到一个点 $(x_k, y_k)$ 使得直线的截距最大
由于斜率和横坐标皆不满足单调性，可以用平衡树等维护，这里使用CDQ分治实现
实现过程如下：
Ⅰ 将数据按照斜率$\frac{A_i}{B_i}$降序排序
Ⅱ 将区间按照操作顺序分为左右两部分处理
Ⅲ 先处理左半部分，维护左半边凸包（注意，此时左半边已按照 $x$ 排序）
Ⅳ 处理左半边对右半边的影响，由于已按照斜率降序排序，所以普通斜率优化即可
Ⅴ 将区间按照 $x$ 排序
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath> using namespace std; const int MAXN = 1e05 + ; const double INF = 1e60;
const double eps = 1e-; int Dcmp (double p) {
if (fabs (p) < eps)
return ;
return p < ? - : ;
} struct CashSt {
double a, b, rate;
double k, x, y;
int index; CashSt () {} bool operator < (const CashSt& p) const {
return Dcmp (x - p.x) == ? Dcmp (y - p.y) < : Dcmp (x - p.x) < ;
}
} ;
CashSt Cash[MAXN];
bool comp (const CashSt& a, const CashSt& b) {
return Dcmp (a.k - b.k) > ;
} int N; double slope (CashSt a, CashSt b) {
if (Dcmp (b.x - a.x) == )
return INF;
return (b.y - a.y) / (b.x - a.x);
}
double f[MAXN]= {};
CashSt Que[MAXN];
int l = , r = ;
CashSt temp[MAXN];
void CDQ (int left, int right) {
if (left == right) {
f[left] = max (f[left], f[left - ]);
Cash[left].y = f[left] / (Cash[left].a * Cash[left].rate + Cash[left].b);
Cash[left].x = Cash[left].y * Cash[left].rate;
return ;
}
int mid = (left + right) >> ;
int p1 = left - , p2 = mid;
for (int i = left; i <= right; i ++)
Cash[i].index <= mid ? temp[++ p1] = Cash[i] : temp[++ p2] = Cash[i];
for (int i = left; i <= right; i ++)
Cash[i] = temp[i];
CDQ (left, mid);
l = , r = ;
for (int i = left; i <= mid; i ++) {
while (l < r && Dcmp (slope (Que[r - ], Que[r]) - slope (Que[r], Cash[i])) < )
r --;
Que[++ r] = Cash[i];
}
for (int i = mid + ; i <= right; i ++) {
while (l < r && Dcmp (slope (Que[l], Que[l + ]) - Cash[i].k) > )
l ++;
f[Cash[i].index] = max (f[Cash[i].index], Cash[i].a * Que[l].x + Cash[i].b * Que[l].y);
}
CDQ (mid + , right);
l = left, r = mid + ;
int p = ;
while (l <= mid && r <= right) {
// if (Dcmp (Cash[l].x - Cash[r].x) < 0 || (Dcmp (Cash[l].x - Cash[r].x) == 0 && Dcmp (Cash[l].y - Cash[r].y) < 0))
if (Cash[l] < Cash[r])
temp[++ p] = Cash[l], l ++;
else
temp[++ p] = Cash[r], r ++;
}
while (l <= mid)
temp[++ p] = Cash[l], l ++;
while (r <= right)
temp[++ p] = Cash[r], r ++;
for (int i = ; i <= p; i ++)
Cash[i + left - ] = temp[i];
} double getnum () {
double num = 0.0;
char ch = getchar ();
double T = 1.0; while (! isdigit (ch))
ch = getchar ();
while (isdigit (ch))
num = num * 10.0 + (ch - '') * 1.0, ch = getchar ();
if (ch == '.') {
ch = getchar ();
while (isdigit (ch))
num = num + (T /= 10.0) * (ch - ''), ch = getchar ();
} return num;
} int main () {
// freopen ("Input.txt", "r", stdin); scanf ("%d%lf", & N, & f[]);
for (int i = ; i <= N; i ++) {
double a = getnum (), b = getnum (), rate = getnum ();
Cash[i].a = a, Cash[i].b = b, Cash[i].rate = rate;
Cash[i].index = i;
Cash[i].k = - a / b;
}
sort (Cash + , Cash + N + , comp);
CDQ (, N);
printf ("%.3f\n", f[N]); return ;
} /*
3 100
1 1 1
1 2 2
2 2 3
*/