P3957

代码如下：

#include<bits/stdc++.h>
#define inf -999999999999ll
#define int long long
using namespace std;
const int MAXN = 5e5 + 10;
int n , d , k;
struct Node {
    int x;
    int s;
};
Node num[MAXN];
int dp[MAXN];
int head , tail , q[MAXN];
   
inline bool check(int g) {
    for(register int i = 1;i <= n;i ++)
        dp[i] = inf;
    head = tail = 0;
    for(register int i = 1;i <= n;i ++)
        q[i] = 0;
    int leng = max(d - g , 1ll);
    int cnt = 0;
    for(register int i = 1;i <= n;i ++) {
        while(cnt < i && num[cnt].x + leng <= num[i].x) {
            while(head <= tail && dp[cnt] >= dp[q[tail]])
                -- tail;
            q[++ tail] = cnt ++;
        }
        while(head <= tail && num[q[head]].x + d + g < num[i].x)
            ++ head;
        q[++ tail] = i;
        dp[i] = dp[q[head]] + num[i].s;
        if(dp[i] >= k)
            return true;
//      cout << head << " " << tail << " " << dp[i] << '\n';
    }
    return false;
}
   
signed main() {
    cin >> n >> d >> k;
    for(register int i = 1;i <= n;i ++)
        cin >> num[i].x >> num[i].s;
//  for(register int g = 0;g <= 1e7;g ++) 
//      for(register int i = 1;i <= n;i ++)
//          for(register int j = 0;j < n;j ++)
//              if(num[j].x + d + g >= num[i].x && num[j] + d - g <= num[i].x)
//                  dp[g][i] = max(dp[g][i] , dp[g][j] + num[i].s);
    int l = 0 , r = 1e9;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    if(l == 1e9)
        cout << -1;
    else
        cout << l;
    return 0;
}