被普及题支配了。。。

原来写了好多次假队列。。。还过了好几道单调队列和斜率优化。。。不懂为啥。。

ll h, t, a[MAXN*5], n, d, p[MAXN*5], ans = -1, k, q[MAXN*5];
ll dp[MAXN*5];

inline void insert(int x) {
  while (h <= t && dp[x] > dp[q[t]]) --t;
  q[++t] = x;
}

inline void erase(int x) {
  if (h <= t && q[h] == x) ++h;
}

inline bool check(int x) {
  int L = max(1, d - x), R = d + x, l = 0, r = 0; h = 1, t = 0;
  lop(i,1,n) {
    while (p[i] - p[r] >= L) insert(r++);
    while (p[i] - p[l] > R) erase(l++);
    dp[i] = a[i] + (h <= t ? dp[q[h]] : -infl);
    if (dp[i] >= k) return 1;
  }
  return 0;
}

int main() {
  in, n, d, k;
  lop(i,1,n) in, p[i], a[i];
  int l = 0, r = max(p[n] - d, d - p[1]);
  while (l <= r) {
    if (check(mid)) ans = mid, r = mid-1;
    else l = mid+1;
  }
  out, ans;
  return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注