AcWing 472. 跳房子
原题链接
中等
作者:
cui_zixu
,
2024-01-14 15:44:10
,
所有人可见
,
阅读 35
#include <iostream>
#include <cstring>
#define x first
#define s second
using namespace std;
typedef long long LL;
typedef pair <int,int> PII;
const int N = 500010;
int n,d,k;
PII a[N];
LL f[N];
bool check (int x) {
int L = max (d - x,1),R = d + x;
f[0] = 0;
for (int i = 1;i <= n;i++) {
f[i] = -1e18;
for (int j = i - 1;j >= 0;j--) {
if (a[j].x + R < a[i].x) break;
if (a[j].x + L > a[i].x) continue;
f[i] = max (f[i],f[j] + a[i].s);
}
if (f[i] >= k) return true;
}
// cout << x << ' ' << ans << endl;
return false;
}
int main () {
cin >> n >> d >> k;
for (int i = 1;i <= n;i++) cin >> a[i].x >> a[i].s;
int l = 0,r = 20000;
while (l < r) {
int mid = l + r >> 1;
if (check (mid)) r = mid;
else l = mid + 1;
}
if (l == 20000) puts ("-1");
else cout << l << endl;
return 0;
}