laekov

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);

}