题意

你从一个二维平面上开始做自由落体运动。重力加速度 $g=10m/s^2$，但是你可以随时调整你在水平方向上的分速度 $v_x \in [-1,1]$。你一开始在点 $(sx,sy)$，但是平面上有 $n$ 个云朵，第 $i$ 个位于 $(x_i,y_i)$，有密度 $c_i$。表示如果你到了 $(x_i,y_i)$，会立刻停止运动 $c_i$ 秒，并在 $c_i$ 秒后将竖直方向分速度重置为 $0$。要求你控制这个人，使得在落到 $y=0$ 的时间尽量大。

$n \leq 5 \times 10^4,x_i,y_i \leq 10^4$。

题解

考虑 dp。设 $f_i$ 表示到达云朵 $i$ 的最长时间。我们将所有云朵按照 $y_i$ 排序，转移考虑枚举 $j$ 可以到达 $i$，发现必须满足

$$ \frac{1}{2}g\Delta x^2 \leq \Delta y $$

所以这告诉我们有用的 $\Delta x$ 只有 $O(\sqrt y)$ 个！枚举这样的 $\Delta x$，相当于现在我们可以从 $x_j = x_i\pm \Delta x, y_j \geq y_i+5\Delta x^2$ 的点转移。

直接转移复杂度看起来还是 $O(n^2)$ 的，但是我们发现，对于 $x_j$ 相等的所有点，由于都可以到达 $i$，所以我们贪心选择最下面的点经过一定是最优的（因为这样会经过最多的云朵，也会减速最多次），所以我们只需要对于每个横坐标维护一下这些横坐标的点，转移二分到 $\geq y_i + 5 \Delta x^2$ 的位置然后从这个点转移即可。复杂度 $O(n\sqrt n \log n)$ 但是很难跑满。

代码

#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e5 + 5;
const int MAX = 20000 + 5;
int n;
int sx,sy;

struct Node{
    int x,y,c;
    Node(int x=0,int y=0,int c=0) : x(x),y(y),c(c) {}
}a[MAXN];

DB f[MAXN];
std::vector<P<int,int> > S[MAXN];

inline void insert(int i){
    int o = a[i].x+MAX;
    S[o].pb(-a[i].y,i);
}

inline int query(int x,int y){// at x, >= y
    x += MAX;
    int p = std::upper_bound(all(S[x]),MP(-y,(int)1e9))-S[x].begin()-1;
    if(p < 0 || p >= SZ(S[x])) return -1;
    return S[x][p].se;
}

int main(){
    scanf("%d%d%d",&n,&sx,&sy);
    FOR(i,1,n) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
    a[++n] = Node(sx,sy,0);
    std::sort(a+1,a+n+1,[&](const Node &a,const Node &b){return a.y > b.y;});
    f[1] = 0;insert(1);
    FOR(i,2,n){
        int x = a[i].x,y = a[i].y;
        f[i] = -1e100;
        FOR(dx,0,sy){
            if(y+5ll*dx*dx > sy) break;
            int t = query(x-dx,y+5ll*dx*dx);
            if(t != -1){
                f[i] = std::max(f[i],f[t]+std::sqrt((a[t].y-a[i].y)/5.0));
            }
            t = query(x+dx,y+5ll*dx*dx);
            if(t != -1){
                f[i] = std::max(f[i],f[t]+std::sqrt((a[t].y-a[i].y)/5.0));
            }
        }
        if(f[i] != -1e100){
            f[i] += a[i].c;
            insert(i);
        }
    }
    DB ans = -1e100;
    FOR(i,1,n) ans = std::max(ans,f[i]+std::sqrt(2.0*a[i].y/10));
    printf("%.10f\n",ans);
    return 0;
}