cdq分治第二题。
最初没看清题所以一直不会做。晕。
cdq教程里的模板题。
显然所有卖都是卖完，买都是把钱买光。
f[i]表示第i天结束后最多持有b卷的数量，ans表示当前最多能赚到的rmb。
方程是：
f[i] = max(ans, f[j] * r[j] * a[i] + f[j] * b[i]) / (a[i] * r[i] + b[i])。
移项得：
f[j] = -(a[i]/b[i]) * (r[j] * f[j]) + (r[i] * a[i] + b[i]) / b[i] * f[j]。
把r[j]*f[j]看作x，把f[j]看作y，好像可以斜率优化了。
不急，f[j]好像没有单调性吧？不对，好像a[i]/b[i]也没有单调性！？
平衡树维护凸壳？想起了上回那道hnoi的作业，调了一晚上，怎么能这样。
然后，其实可以cdq。
每次对右边有影响的是左边的凸壳，所以先跑左边，计算左边对右边的影响，再跑右边。这回是中序遍历，而不是Mokia那题的后序。
原来cdq可以这么神奇。
然后又把凸壳写丑了TT。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100009;
double ans, s, f[maxn], a[maxn], b[maxn], r[maxn];
int n, h[maxn], tmp[maxn], t;
inline double getx(const int& i) {
return f[i] * r[i];
}
inline double gety(const int& i) {
return f[i];
}
inline double getk(const int& i, const int& j) {
return (gety(j) - gety(i)) / (getx(j) - getx(i));
}
inline bool cmpP(const int& a, const int& b) {
return f[a] * r[a] < f[b] * r[b] || (f[a] * r[a] == f[b] * r[b] && f[a] < f[b]);
}
int getmax(int l, int r, double k) {
-- r;
if (l == r)
return h[l];
-- r;
if (k < getk(h[r], h[r + 1]))
return h[r + 1];
while (l < r) {
int mid = (l + r) >> 1;
if (k < getk(h[mid], h[mid + 1]))
l = mid + 1;
else
r = mid;
}
return h[l];
}
inline double mulx(const int& a, const int& b, const int& c, const int& d) {
double x1 = getx(b) - getx(a), y1 = gety(b) - gety(a);
double x2 = getx(d) - getx(c), y2 = gety(d) - gety(c);
return x1 * y2 - x2 * y1;
}
void cdq(int l, int r, int& tb, double& ans) {
if (l + 1 == r) {
double fn = 1.0 / (:: r[l] * a[l] + b[l]);
if (fn > f[l])
f[l] = fn;
h[(tb = r) - 1] = l;
ans = f[l] * (:: r[l] * a[l] + b[l]);
}
else {
int bl, br, mid = (l + r) >> 1;
double sl, sr;
cdq(l, mid, bl, sl);
ans = sl;
for (int i = mid; i < r; ++ i) {
int j = getmax(l, bl, -a[i] / b[i]);
double fn = max(sl, f[j] * (:: r[j] * a[i] + b[i])) / (:: r[i] * a[i] + b[i]);
if (fn > f[i]) {
f[i] = fn;
}
ans = max(ans, f[i] * (:: r[i] * a[i] + b[i]));
}
cdq(mid, r, br, sr);
ans = max(ans, sr);
tb = l;
for (int i = l, j = mid; i < bl || j < br;) {
int k;
if (j == br || (i < bl && getx(h[i]) < getx(h[j])))
k = h[i ++];
else
k = h[j ++];
while (tb > l + 1 && mulx(tmp[tb - 2], tmp[tb - 1], tmp[tb - 2], k) >= 0)
-- tb;
tmp[tb ++] = k;
}
for (int i = l; i < tb; ++ i)
h[i] = tmp[i];
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
memset(f, 0, sizeof(f));
scanf("%d%lf", &n, &s);
for (int i = 0; i < n; ++ i)
scanf("%lf%lf%lf", a + i, b + i, r + i);
cdq(0, n, t, ans);
printf("%.3lf\n", ans * s);
}