CSFBF的样例什么错误都查不出来!
#include<bits/stdc++.h>
using namespace std;
long long n, d, k,dp[1000000];
struct node {
int a, b;
}a[1000000];
struct queue {
int q[1000000];
int tail, head;
inline void ch() { if (head > tail)exit(1145141145); if (head < 0 || tail < 0 || head>999999 || tail>999999) exit(314159265); }
inline void init() { head = 0, tail = 0; }
inline void pub(int n) { q[++tail] = n; ch(); }
inline void puf(int n) { q[head--] = n; ch(); }
inline void pob() { --tail; ch(); }
inline void pof() { head++; ch(); }
inline void gte() { tail = head; }
inline int f() { return q[head + 1]; }
inline int b() { return q[tail]; }
inline int s() { return tail - head; }
}q;
bool cmp(node a, node b)
{
return a.a != b.a ? a.a<b.a : a.b>b.b;
}
bool check(int mid)
{
q.init();
memset(dp, 0x80, sizeof(dp));
dp[0] = 0;
int l = max(1ll, d - mid), r = d + mid;
for (int i = 1, j = 0; i <= n; i++)
{
while (a[i].a - a[j].a >= l &&j<i)
{
if (dp[j] != 0x8080808080808080)
{
while (q.s() && dp[q.f()] <= dp[j]) //这行错了
//while (q.s() && dp[q.b()] <= dp[j]) 正确代码
q.pob();
q.pub(j);
}
j++;
}
while (q.s() && a[q.f()].a + r < a[i].a)
q.pof();
if (q.s())
dp[i] = dp[q.f()] + a[i].b;
if (dp[i] >= k)
return 0;
}
return 1;
}
int main()
{
cin >> n >> d >> k;
for (int i = 1; i <= n; i++)
cin >> a[i].a >> a[i].b;
sort(a + 1, a + n + 1, cmp);
int l = 0, r = 1000000000;
while (l <= r)
if (check(l + r >> 1))
l = (l + r >> 1) + 1;
else
r = (l + r >> 1) - 1;
if (l == 1000000001)
cout << -1;
else
if (!check(r))
cout << r;
else
cout << l;
}//样例全过,能得70分