思路是用斜率优化+二分答案

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e6+5;
const double inf = (double)1e28;
double x[maxn]={},R[maxn]={},c[maxn]={},m,dp[maxn]={},ans = inf;
int que[maxn]={},rear =  0;
int n;
inline double getk( double &ybig, double &xbig, double &ysmall, double &xsmall ){
    return (ybig - ysmall) / (xbig - xsmall);
}
double slope[maxn]={};
int main(){
    cin >> n >> m;
    register double k; register int l , r , mid;
    for(register int i = 1; i <= n; i ++ ) scanf("%lf%lf%lf",&x[i],&R[i],&c[i]);
    int st = n;
    while(!(x[st]+R[st]>=m)) st--;
    dp[st] = dp[0] = c[st], que[rear++] = 0, que[rear++] = st, slope[1] = 0,slope[0] = inf;
    for(register int i = st-1; i >= 1; i -- ){
        k =  - ( 1.0 / 2.0 / sqrt( R[i] ) );
        l = 1, r = rear-1;
        while(l < r){
            mid = ( l + r  + 1 ) >> 1;
            if( slope[mid] <= k){
                r = mid-1;
            }else{
                l = mid;
            }
        }
        if( r == 0 ) r = 1;
        if(x[i]+R[i]>=m) dp[i] = c[i];
        else dp[i] = c[i] + dp[que[r]] - k * (x[que[r]]-x[i]);
        while( getk(dp[i],x[i],dp[que[rear-1]],x[que[rear-1]]) >= slope[rear-1] ) rear--;
        que[rear++] = i;
        if(rear-1!=1) slope[rear-1] = getk(dp[i],x[i],dp[que[rear-2]],x[que[rear-2]]);
    }
    cout << fixed << setprecision(3) << dp[1];
    return 0;
}