提交记录

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <deque>

using namespace std;

typedef long long ll;

const int N = 500010;

int n, d, k, x[N], s[N];
ll f[N];

bool in(int x, int l, int r) {
	return x >= l && x <= r;
}

bool check(int g) {
	memset(f, 0, sizeof(f));
	deque<int> q;
	int l = max(d - g, 1), r = d + g;
	q.push_back(0);
	for (int i = 1; i <= n; i++) {
		int j = q.back() + 1;
		while (j < i && !in(x[i] - x[j], l, r)) j++;
		// 寻找当前最近的未入队合法点，没找到 j = i
		while (!q.empty() && x[i] - x[q.front()] > r) q.pop_front();
		for (; in(x[i] - x[j], l, r); j++) {
			// 此时若 j = i 说明当前没有未入队合法点
			// x[i] - x[j] = 0 不在 [l, r] 内
			// 若 j < i 说明当前有未入队合法点，依次入队
			while (!q.empty() && f[j] >= f[q.back()]) q.pop_back();
			// pop 距离过远的点，但保留距离过近的点（后面留着接着用）
			q.push_back(j);
		}
		if (q.empty() || !in(x[i] - x[q.front()], l, r)) continue;
		// 当前没有（合法的）点
		f[i] = f[q.front()] + s[i];
		if (f[i] >= k) return 1;
	}
	return 0;
}

int main() {
	scanf("%d%d%d", &n, &d, &k);
	ll tmp = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &x[i], &s[i]);
		tmp += max(s[i], 0);
	}
	if (tmp < k) {
		printf("-1");
		return 0;
	}
	int l = 0, r = N;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid - 1;
		else l = mid + 1;
	}
	printf("%d", l);
	return 0;
}