题解

（请在此补充题目的中文题解与思路描述。）

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>

using namespace std;

const int MAXN = 1E5 + 10;

int n;
double a[MAXN], b[MAXN], rate[MAXN], c[MAXN], cs[MAXN];

struct Line
{
    double k = 0, b = 0;

    double f(double x) const { return k * x + b; }
};

Line d[4 * MAXN];

double get(int i)
{
    double x = cs[i];
    Line ans;
    int p = 1, beg = 0, end = n - 1;
    while (true)
    {
        if (d[p].f(x) > ans.f(x))
            ans = d[p];
        if (beg == end)
            break;
        int lch = 2 * p, rch = 2 * p + 1;
        int mid = (beg + end) / 2;
        if (i <= mid)
        {
            p = lch;
            end = mid;
        }
        else
        {
            p = rch;
            beg = mid + 1;
        }
    }
    return ans.f(x);
}

void apply(Line line)
{
    auto _apply = [&line](auto &&self, int p, int beg, int end) -> void
    {
        // if (end < l || beg > r)
        // return;

        int lch = 2 * p, rch = 2 * p + 1;
        int mid = (beg + end) / 2;

        // if (beg >= l && end <= r)
        {
            bool better_beg = line.f(cs[beg]) > d[p].f(cs[beg]);
            bool better_end = line.f(cs[end]) > d[p].f(cs[end]);

            if (!better_beg && !better_end)
                return;
            if (better_beg && better_end)
            {
                d[p] = line;
                return;
            }

            if (line.f(cs[mid]) > d[p].f(cs[mid]))
            {
                swap(d[p], line);
                swap(better_beg, better_end);
            }
            better_beg ? self(self, lch, beg, mid) : self(self, rch, mid + 1, end);
        }
        // else
        // {
        //     self(self, lch, beg, mid);
        //     self(self, rch, mid + 1, end);
        // }
    };

    _apply(_apply, 1, 0, n - 1);
};

int main()
{
#ifdef ZHXS_LOCAL
    freopen("in.txt", "r", stdin);
#endif // ZHXS_LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int s;
    cin >> n >> s;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i] >> rate[i];
        c[i] = a[i] / b[i];
        cs[i] = c[i];
    }
    sort(cs, cs + n);

    double last_dp = s;

    for (int i = 0; i < n; i++)
    {
        int rk = lower_bound(cs, cs + n, c[i]) - cs;
        last_dp = max(last_dp, get(rk) * b[i]);
        double b_cnt = last_dp / (a[i] * rate[i] + b[i]);
        double a_cnt = b_cnt * rate[i];
        apply({a_cnt, b_cnt});
        // printf("i = %d, f = %.3lf\n", i + 1, last_dp);
    }

    cout << fixed << setprecision(3) << last_dp << endl;
    return 0;
}