P3957 跳房子 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • cwnuaa
    思路不错,程序太长
  • Victorique
    程序太长,思路不错
  • 钾钾钾硫碳03
    思路太长,程序不错
  • hongzy
    程序不错,思路太长
  • Kaori
    思路太长,程序太长
  • Mr_Wu
    ...
  • Fuji__Syusuke
    程序太长,思路不错
  • bcku1
    思路太长,程序太长
  • zhouwc
    程序太长,思路不错
  • nstk0513
    其实这是一个很不错的题解,思路很详细,代码长短是个人习惯问题,又不是拿来抄的
作者: Tweetuzki 更新时间: 2017-11-25 14:04  在Ta的博客查看    105  

这题是第四题,对于我这种蒟蒻来讲是不可能 AC 的,所以先想着骗分。什么时候不能得到目标分数呢?如果所有正数分数都加起来还小于目标分数,那就得不到目标分数。所以先特判 $-1$。

再看看这一题,我想起了 NOIP2015 提高组的“跳石头”,那题不是二分吗?这题也好像啊……于是果断使用二分求解。确定下来二分了,那么就来考虑,怎样判断二分的这个答案可不可以,显然使用动态规划。

$dp[i]$ 表示跳到第 $i$ 个格子时所能得到的分数最大值,若跳不到该格,则 $dp[i]=-\infty$。为了动规方便,再加入起点的格子,显然,起点格子离原点的距离为 $0$,格子上的值也为 $0$。状态转移方程:设 $max(l,r)$ 表示 $[l,r]$ 区间内能跳到的格子中的最大值,则 $dp[i]=\max($点 $i$ 到原点的距离 $-mid$,点 $i$ 到原点的距离 $+mid)$。

用没有优化的 DP,时间复杂度是二维的,对于 $50\%$ 的数据可以过,但是对于另外 $50\%$ 的数据 $n=500000$,即使两秒的时限也是超得不爱超了。怎么优化 DP 呢?

有一个叫单调队列的东西,专门取区间内的最大最小值。在 POJ 上,有一题叫做Sliding Window,就是单调队列的模板题。单调队列要想优化 DP,必须得保证 $l$ 和 $r$ 是单调递增或递减的。而在本题中,在向右 DP 时,上述的状态转移方程在 $dp[i]=\max($点 $i$ 到原点的距离 $-mid$,点 $i$ 到原点的距离 $+mid)$ 的 $mid$ 不变的情况下,随着 $i$ 离原点越来越远,$l$ 和 $r$ 越来越大,所以也是单调递增的。这样一优化,DP 的时间复杂度就降至一维,对于最大的 $n=500000$,就能在 2 秒的时限内轻松通过了。

upt: 感谢各位指正,现以修复代码中原有的 bug。我原来犯的错误有:

  1. dp 数组初始值不能设为 $-1$,应该设为 $-\infty$,在代码中体现为 $\text{0x8080808080808080}$。
  2. 二分的右边界应该取 $d$ 与第 $n$ 个格子到原点的距离的较大值,因为 $d$ 与第一个格子间距离可能大于第 $n$ 个格子到原点的距离。(感谢 @Bartholomew 的 Hack 数据 1 42 14 20 23

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn=500000;
const long long neInf=0x8080808080808080;
struct gezi {
    int juli;
    int zhi;
} a[maxn+1];
long long dp[maxn+1];
int q[maxn+1];
int n,d,k,lbound,rbound,ans=-1;
long long sum;

void kuaidu(int &p) {
    char c;
    int f=1;
    p=0;
    do {
        c=getchar();
        if (c=='-')
            f=-1;
    } while (c<'0'||c>'9');
    do p=p*10+c-'0', c=getchar();
    while (c>='0'&&c<='9');
    p=p*f;
}

void init() {
    cin>>n>>d>>k;
    for (int i=1; i<=n; i++) {
        kuaidu(a[i].juli);
        kuaidu(a[i].zhi);
        if (a[i].zhi>0)
            sum+=a[i].zhi;
    }
    rbound=max(a[n].juli,d);
}

long long dynamic_programming(int zuo, int you) {
    memset(dp,0x80,sizeof(dp));
    dp[0]=0;
    memset(q,0,sizeof(q));
    int tou=1, wei=0, j=0;
    /*for (int i=1; i<=n; i++)
        for (int j=0; j<i; j++)
            if (a[i].juli-a[j].juli>=zuo&&a[i].juli-a[j].juli<=you&&dp[j]!=neInf)
                dp[i]=max(dp[i],dp[j]+a[i].zhi);*/
    for (int i=1; i<=n; i++) {
        while (a[i].juli-a[j].juli>=zuo&&j<i) {
            if (dp[j]!=neInf) {
                while (tou<=wei&&dp[q[wei]]<=dp[j])
                    wei--;
                q[++wei]=j;
            }
            j++;
        }
        while (tou<=wei&&a[i].juli-a[q[tou]].juli>you)
            tou++;
        if (tou<=wei)
            dp[i]=dp[q[tou]]+a[i].zhi;
    }
    long long num=neInf;
    for (int i=1; i<=n; i++)
        if (dp[i]>num)
            num=dp[i];
    return num;
}

int main() {
    //freopen("jump.in","r",stdin);
    //freopen("jump.out","w",stdout);
    init();
    if (sum<k) {
        cout<<"-1"<<endl;
        return 0;
    }
    while (lbound<=rbound) {
        int mid=(lbound+rbound)/2;
        int zuobianjie=max(1,d-mid);
        int youbianjie=d+mid;
        long long num=dynamic_programming(zuobianjie,youbianjie);
        if (num<k)
            lbound=mid+1;
        else {
            ans=mid;
            rbound=mid-1;
        }
    }
    cout<<ans<<endl;
    //fclose (stdin);
    //fclose (stdout);
    return 0;
}

评论

  • 姬小路秋子
    考场上的一眼题会超纲??
  • 姬小路秋子
    这题我想的时间还不如t3久
  • pmt2018
    %%%djq
  • BBencg
    @a3_de_liefde_zz 这是我们学校大佬,他在装弱你也看不出来?你有他强??
  • bs2019lixuheng
    @a3_de_liefde_zz人家装弱不行?
  • ybwowen
    %%%DJQ!
  • wsr_oi
    %%%装弱的命案。。。
  • 虫合
    sto @a3_de_liefde_zz orz
  • Panthera_AFO
    @BBencg 妈耶你怎么知道他没有人家强?
  • 糖豆小王子
    哈哈哈
作者: djq_cpp 更新时间: 2017-11-13 11:02  在Ta的博客查看    29  

深感此题超纲。。。

首先注意到,如果花费g枚金币可以得到k分,那么花费g+1枚也一定可以。也就是说,可以二分g。

那么,如何判断花费g枚金币是否可行呢?

考虑dp,dp[i]表示跳到格子i时获得的最大分数。

显然可以这样更新:

dp[0]=0LL;
for(int i=1;i<=n;i++){
    dp[i]=-INF;
    for(int j=0;j<i;j++)
    if(pos[i]-pos[j]>=mind&&pos[i]-pos[j]<=maxd)
    dp[i]=max(dp[i],dp[j]+s[i]);
}

这是O(n^2)的,总体复杂度O(n^2*log(ans)),能过50%的数据。

int l=0,r=0;
for(int i=1;i<=n;i++){
    dp[i]=-INF;
    while(pos[i]-pos[r]>=mind)r++; 
    while(pos[i]-pos[l]>maxd)l++; 
    for(int j=l;j<r;j++)
    dp[i]=max(dp[i],dp[j]);
    dp[i]+=s[i];
}

我们发现,dp[i]是由dp[l...r)的最大值转移而来,其中区间[l...r)随着i的增加只会向右滚动。另外dp[i]可以写成max(dp[k])(l<=k<r)+s[i]的形式。这……不是deque优化的充分条件么? 使用一个单调队列维护一下[l...r)内的dp值即可。

单调队列优化的dp时间复杂度为O(n)线性,总复杂度为O(n log(ans))。

为了防止被ccf老爷机卡掉,还是贴手写deque(其实就几行)吧……【djq在场上没有手写担心被卡常】

#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF=1e9+7;
int n,pos[500005],num[500005];
ll dp[500005];
int frt,rr;
pair<ll,int> cur[500005];
inline void ins(pair<ll,int> ele){
    while(frt<rr&&cur[rr-1]<ele)rr--;
    cur[rr++]=ele;
}
inline void era(pair<ll,int> ele){
    if(frt<rr&&cur[frt]==ele)frt++;
}
inline ll maxi(){
    return frt>=rr?(-1LL<<60):cur[frt].first;
}
bool check(int mind,int maxd,int lim){
    int l=0,r=0;
    frt=rr=0;
    dp[0]=0LL;
    rep1(k,n){
        while(pos[k]-pos[r]>=mind){
            ins(MP(dp[r],r));r++;
        }
        while(pos[k]-pos[l]>maxd){
            era(MP(dp[l],l));l++;
        }
        dp[k]=maxi()+num[k];
        if(dp[k]>=lim)return true;
    }
    return false;
}
int main(){
//    freopen("jump.in","r",stdin);
//    freopen("jump.out","w",stdout);
    int d,lim;
    scanf("%d%d%d",&n,&d,&lim);
    rep1(k,n)scanf("%d%d",&pos[k],&num[k]);
    int l=0,r=INF;
    while(l<r){
        int mid=(l+r)>>1;
        if(check(max(d-mid,1),d+mid,lim))r=mid;
        else l=mid+1;
    }
    printf("%d\n",r==INF?-1:r);
    return 0;
}

评论

  • kilikili
    nice
  • kilikili
    very nice
  • 六得不行
    %%%
  • lin__zj
    nice 兄dei
  • sundy
    为什么r=1005呢?请问怎么分析出来的呢?
  • 张曜玺
    r=1005你在搞笑?
  • Kai_Admin
    没有-1这个点哦
  • Kai_Admin
    我输-1爆零
  • 单志远
    考虑一下范围就可以了(数据不是专门卡的话) 单调队列是正解 考虑范围优化算是取巧了
  • HenryHuang
    CCF对普及组太仁慈了
作者: 文飞扬 更新时间: 2018-04-29 19:50  在Ta的博客查看    26  

这道题目是2017年普及组第四题,难度是比较大的,作为一名竞赛选手,碰到这样的难题,应该根据自己的知识情况,去尽可能获得更多的分数,下面一一分析,也可参见跳房子(noip2017普及T4)解题报告

1、假如我对于什么二分法,搜索,动态规划统统不知道,地地道道一个小白,那么,我也可以这么分析,如果所有格子中的正数之和低于所需分数,显然是不能到达的,那么直接输出-1,否则的话,我可设想,很可能需要把除了最后面分数为负的格子以外的所有格子都跳到(有点非完美算法的思想),因此,可以用如下伪代码实现;

if(所有格子正数和小于所需分数)
    输出-1;
else
    求出从起点到最后一个正数格子的之间跳动的最小距离mind和最大距离maxd
    输出d-mind和maxd-d之间较大的一个数

这样,应该能得一些分数。

2、求花多少金币来改造,显然,最少不花钱,最多呢就是一次能跳到最后一个格子距离的金币,而且花少量金币能完成的话,花更多金币也肯定能完成,这是一个很宽的范围,要从宽范围里面选择一个数字,毫无疑问,二分法是最快的,因此,程序的结构就是一个二分再加一个判断,结构如下。

int main()
{
    int i,ans=-1,l,r,m;
    cin>>n>>d>>k;
    for(i=1; i<=n; i++)
        cin>>a[i][0]>>a[i][1];
    l=0, r=a[n][0];
    m=(l+r)/2;
    while(l<=r)
    {
        if(check(m))//判断m是否符合要求 
        {
            ans=m;
            r=m-1;
        }
        else
        {
            l=m+1;
        }
        m=(l+r)/2;
    }
    cout<<ans;
    return 0;
}

3、如何来判断某个金币数是否符合要求,怎么办?发现在能跳到的情况下,每个格子只有两种选择,要么跳到这个格子,要么不跳到这个格子,而且每个格子也可以越过一些格子跳到后面的一些格子去,因此跳到每个格子的分数有非常多的可能性,可用深度优先搜索来搜一下试试,然而,直接搜索的话,巨量的搜索树,肯定让程序挂掉,还是采取记忆化搜索方法,如果搜到这个格子发现以前搜过,而且分数比这次更高,那就直接返回,代码如下,可以得60分。

int f[500005],a[500005][2],n,d,k,ok,lpos,rpos;
//i表示搜索第i格,pos目前位置,sum目前得分
void dfs(int i, int pos, int sum)
{
    if(ok || i>n)
        return;
    if(a[i][0]-pos>rpos)//不能跳那么远 
        return;
    if(a[i][0]-pos<lpos)//比最短跳远距离还短,跳下格
    {
        dfs(i+1,pos,sum);
        return;
    }
    if(a[i][1]+sum>=k)
        ok=1;
    else if(a[i][1]+sum>f[i])
        f[i]=a[i][1]+sum;
    else
        return;//以前搜索分数更高,直接返回 
    dfs(i+1, pos, sum);//不选 i号格子 
    dfs(i+1, a[i][0], sum+a[i][1]);//选择 
}
bool check(int g)
{
    ok=0;
    lpos = d-g;
    rpos = d+g;
    if(lpos<=0)
        lpos = 1;
    memset(f,-127,sizeof(f));
    dfs(1,0,0);
    return ok;
}

4、想要得满分,那就只能动态规划了,设f[i]表示跳到第i格的最高得分,那么,f[i]肯定是从它前面那些能够跳到的格子里面得分最高的那个格子跳过来的,可以从i号格子前面第一个格子开始查找得分最高的格子,直到超过最大可跳范围为止,把这个区间的最大得分加上自己本身的分数就是第i格的最高分数了。另外,由于数据量巨大,开始搜索的右边值可以适当设小,这里设成了1005,设成10005也可以,这个程序可以满分。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long f[500005],a[500005][2],n,d,k,ok,lpos,rpos;

bool check(int g)
{
    lpos = d-g;//跳的最短距离 
    rpos = d+g;//跳的最长距离 
    if(lpos<=0)
        lpos = 1;
    memset(f,-127,sizeof(f));//设为很小的负数
    f[0]=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=i-1; j>=0; j--)
        {
            if(a[i][0]-a[j][0]<lpos) continue;
            if(a[i][0]-a[j][0]>rpos) break;
            f[i]=max(f[i],f[j]+a[i][1]);
            if(f[i]>=k)
                return 1;
        }
    }
    return 0;
}
int main()
{
    int i,ans=-1,l,r,m;
    scanf("%lld%lld%lld",&n,&d,&k);
    for(i=1; i<=n; i++)
        scanf("%lld%lld",&a[i][0],&a[i][1]);
    l=0, r=1005;
    m=(l+r)/2;
    while(l<=r)
    {
        if(check(m))
        {
            ans=m;
            r=m-1;
        }
        else
        {
            l=m+1;
        }
        m=(l+r)/2;
    }
    cout<<ans;
    return 0;
}

5、要想效率更高的话,考虑到f[i]总是从前面可跳区间的最大值跳过来,随着i往后面走,这个区间也往后面走,如果采用单调队列,速度会快很多,但是需要用到双端队列来构造单调队列,代码相对复杂一点,如下所示:

bool check(int g)
{
    lpos = d-g;//跳的最短距离 
    rpos = d+g;//跳的最长距离 
    if(lpos<=0)
        lpos = 1;
    memset(f,0,sizeof(f));
    deque<int> dq;//定义一个双端队列 
    int cur=0;//当前待入队的格子编号 
    for(int i=1; i<=n; i++)
    {
        for(;cur<i&&a[i][0]-a[cur][0]>=lpos; cur++)
        {
            if(dq.empty())
                dq.push_back(cur);
            else
            {
                while(!dq.empty()&&f[cur]>=f[dq.back()])
                    dq.pop_back();
                dq.push_back(cur);
            }
        }
        while(!dq.empty()&&a[i][0]-a[dq.front()][0]>rpos)
            dq.pop_front();
        if(!dq.empty())
            f[i]=f[dq.front()]+a[i][1];
        else
            f[i]=-999999999999;
        if(f[i]>=k)
            return 1;
    }
    return 0;
}

娄底一中刘文博 2018.4.29

评论

  • Gang_Leader
  • 陈嘉熙
    CFF???
  • 小写的吴辜
    NOIp 2018 T3 > NOIp 2017 T4 > NOIp 2018 T4 > NOIp 2017 T3
  • Neptune_Disaster
    CFF可还行
  • 超级小周
    蹦跶的越欢...
作者: NOIPOIER 更新时间: 2018-11-08 11:34  在Ta的博客查看    12  
考场上看到这题是绝望的(T_T)
连O(2^n)的深搜都炸了……
还好今年不考普及组了(貌似提高更……)
再看一眼数据范围
对于第 1, 2 1,2组测试数据, n ≤ 10;
对于第 3, 4, 53,4,5 组测试数据, n ≤ 500
对于第 6, 7, 86,7,8 组测试数据, d = 1
对于全部的数据满足1 ≤ n ≤ 500000, 1 ≤ d ≤2000,
1 ≤ x_i, k ≤ 10^9, |s_i| < 10^5
我们循序渐进
M1 0(骗分,最理所当然的想法)
直接输出-1,然而CFF呵呵,没有-1;
M2 20
看似就像是比较好大的,然而 我就死在了这上面。
具体思路dfs枚举取或不取
比较答案与k的大小
然后就有20分了
(考场上太弱,dfs都没打完)
M3 80(开始变的玄学……)
首先,不(hen)难看出,答案有单调性……
对于一个 g
机器人蹦跶的范围【max(0,d-g),d+g】
显然 g越大
机器人会蹦跶的越欢……
于是,就有常用方法——二分答案的诞生了
while(l!=r){
    long long mid=(l+r)/2;
    if(check(mid))r=mid;
    else l=mid+1;
}
if(!check(l)){
    printf("-1");
    return 0;
}
else printf("%lld",l);
没错,就长这样,整个程序的————关键落在了
check上。
如何check?想(kan)一(ti)想(jie)就会发现dp
这显然是一个最优化问题,
设dp【i】为跳到第i个点时机器人最大得分
初始时,dp【i】=-inf;dp【0】=0;
——————————————————————————
转移:
显然 dp【i】=dp【j】+val【i】;
(val【i】为第i个点的得分)
j显然是有条件的
还记的蹦跶的范围吗?
【max(0,d-g),d+g】
pos【j】应该在【pos【i】-d-g,pos【i】-max(0,d-g)】之间
pos【i】表示第i个点的位置
所以我们就有了核心代码————————————
bool check(long long mid){
long long l=max(0,d-mid);
long long r=d+mid;
for(int i=1;i<=n;i++)
{
for(int j=0;j<i;j++)
if(pos[j]<=pos[i]-l&&pos[j]>=pos[i]-r)
dp[i]=max(dp[i],dp[j]+val[i]);
if(dp[i]>=k)return 1;
}
return 0;
}
复杂度O(n^2*logSmax)
好像很快的样子?
500000的数据量可不是吃素的……
洛谷上都不支持下载了……
1min都跑不完……
非常令人绝望……
于是再想(kan)一(ti)想(jie)
就有了M4 100
出锅出在哪?二分同学已经很优秀了,而dp同学却颓得不像样
我们得优化它
M4 100 正解 二分答案+dp+单调队列优化 O(nlogSmax)
终极玄学——————————
我们还得在check函数上做手脚
dp【i】=dp【j】+val【i】;
再看一眼状态转移方程
惊奇的发现dp【i】只与dp【j】有关
OI界两个神器,便派上了用场
当dp【i】只与j有关,我们可以使用——————
单调队列(还有一个叫斜率优化,虽然用不到)
假设Q里面front是最优状态
则dp【i】=dp【Q.front()】+val【i】;
瞬间降维,唯一的问题就是维护Q了
首先,每一个状态(即i)只会进出一次
题目要求在区间【pos【i】-d-g,pos【i】-max(0,d-g)】
内求解,显然,太老的得弹出去,太年轻的不让进
while(Q.size()&&(pos[Q.front()])<pos[i]-r)
Q.pop_front();//已经超出了下界pos【i】-r
las为最远的待加入的编号
while(pos[las]<pos[i]-r)las++;//还没被加入,就已经出范围了
while(pos[i]-l>=pos[las]&&pos[i]-r<=pos[las]&&las<i)
    {//保证比上界小
        while(Q.size()&&(dp[Q.back()]<=dp[las]
        ||pos[Q.back()]<pos[i]-r))
         //如果值没有当前的大,显然的出队
         //即使值大,不在范围内,也出队
        Q.pop_back();
        Q.push_back(las);
        las++;
    }
 可以证明每一个点只进出一次
 成功降维
 O(n*logSmax)
 全部代码
 #include<bits/stdc++.h>
 using namespace std;
 const long long inf=1e18;
 int n;
long long d,k; 
long long pos[500001],val[500001];
long long dp[500001];
deque<long long> Q;
bool check(long long mid){
if(!Q.empty())Q.clear();
long long l=(d-mid<0?0:d-mid);
long long r=d+mid;
int las=0;
for(int i=0;i<=n;i++)
dp[i]=-inf;
dp[0]=0;
for(int i=1;i<=n;i++)
{
    while(pos[las]<pos[i]-r)las++;
    while(pos[i]-l>=pos[las]&&pos[i]-r<=pos[las]&&las<i)
    {
        while(Q.size()&&(dp[Q.back()]<=dp[las]||pos[Q.back()]       <pos[i]-r))
        Q.pop_back();
        Q.push_back(las);
        las++;
    }
    while(Q.size()&&(pos[Q.front()])<pos[i]-r)
    Q.pop_front();
    if(Q.size()!=0)dp[i]=dp[Q.front()]+val[i];
    if(dp[i]>=k)return 1;
}
return 0;
}
int main(){
    scanf("%d%lld%lld",&n,&d,&k);
    for(int i=1;i<=n;i++)
    scanf("%lld%lld",&pos[i],&val[i]);
    long long l=0,r=pos[n];
    while(l!=r){
        long long mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    if(!check(l)){
        printf("-1");
        return 0;
    }
    else printf("%lld",l);
    return 0;
}
如果你仍然出锅了
!!!!
1: long long是必须的
2:inf得足够大,0x7f7f7f7f太小了
3:取max时,你会发现max(0,d-mid)会CE
因为 0:int d-mid:long long
还是 if语句或?:运算符更安全
4:二分时注意l和r
应该没了吧。
NOIP2018rp++

评论

  • Rousseau_
    orz
  • 裘大大
    666
  • 裘大大
    666
  • 404_notfound
    %%%大佬(我只会骗分)
  • 要写return0!
    第二个题解是错的吧,只有90分
  • lvtianyu123
    垃圾啊,题解那么烂
  • lvtianyu123
    第二个才90!!!
  • lvtianyu123
    猪吗
  • lvtianyu123
    算了算了
  • Bear_Dog_Cat
    不是挺好的吗
作者: 一色彩羽 更新时间: 2017-11-22 17:07  在Ta的博客查看    5  

马上要转c++,再水篇P的题解

当场写了个线段树,写挂了

想到了单调队列,也写挂了

考后才想到怎么写,然而来不及了。。。

正解应该是:二分答案+dp+单调队列优化

状态:f[i]表示最后一个调到i的最大的得分

方程:f[i]:=max{f[j]}+a[i](能从j一下子跳到i)

显然符合条件的f[j]是个区间,所以用个数据结构优化就行了 然而我选择线段树,堆也可以

由于我太菜了。。注释写得可能会比较少。。。

丑陋的线段树代码(lg的数据不能AC,但能过qbxt的数据和官方数据):

uses math;
const
  p=-233333333;
type
  tree=record
  l,r:longint;
  sum:int64;
end;
var
  b,x:array[0..500001]of int64;
  f:array[0..500001]of int64;
  a:array[0..3000001]of tree;
  n,m,k,i,j,ans:longint;
  l,r,mid,sum:int64;
procedure build(k,l,r:longint);
var
  mid:longint;
begin
  a[k].l:=l; a[k].r:=r; a[k].sum:=p;
  if l=r then exit;
  mid:=(l+r) >> 1;
  build(k*2,l,mid);
  build(k*2+1,mid+1,r);
end;//建树
procedure add(k,l,r,x:longint);
var
  mid:longint;
begin
  if a[k].l=a[k].r then 
    if a[k].l=l then 
      begin
        a[k].sum:=x;
        exit;
      end;
  mid:=(a[k].l+a[k].r) >> 1;
  if mid>=l then add(k << 1,l,r,x);
  if mid<r then add(k << 1+1,l,r,x);
  a[k].sum:=max(a[k << 1].sum,a[k << 1+1].sum);
end;//修改
function query(k,l,r:longint):int64;
var
  ans,mid:longint;
begin
  if (a[k].l>=l)and(a[k].r<=r) then exit(a[k].sum);
  ans:=p;
  mid:=(a[k].l+a[k].r) >> 1;
  if mid>=l then ans:=max(ans,query(k << 1,l,r));
  if mid<r then ans:=max(ans,query(k << 1+1,l,r));
  exit(ans);
end;//查询
function check(ans:longint):boolean;
var
  i,j,z,zz:longint;
  l,r:int64;
begin
  if ans>=k then l:=1 else l:=k-ans;
  r:=k+ans;
 // for i:=1 to 2000000 do a[i].sum:=p;
  build(1,0,n);
  add(1,0,0,0);
  z:=0; zz:=-1;
  for i:=1 to n do 
    begin
      while x[z]<x[i]-r do inc(z);
      while x[zz+1]<=x[i]-l do inc(zz);
      if (z<0)or(zz<0)or(z>zz) then continue;
      f[i]:=query(1,z,zz);
      if f[i]<>p then 
        begin
          inc(f[i],b[i]);
          add(1,i,i,f[i]);
        end;
      if f[i]>=m then exit(true);
    end;//dp
  exit(false);
end;
begin
  readln(n,k,m);
  for i:=1 to n do 
    begin
      readln(x[i],b[i]);
      if (b[i]>0)and(sum<=m) then inc(sum,b[i]);
    end;
  if sum<m then
    begin
      writeln(-1);
      halt;
    end; 
  //build(1,0,n);
  ans:=-1;
  l:=0;
  r:=x[n];
  while l<=r do 
    begin
      mid:=(l+r) >> 1;
      if check(mid) then begin ans:=mid;r:=mid-1 end
        else l:=mid+1;
    end;//二分答案
  write(ans);
end.

单调队列维护dp:

var
  x,a,q:array[0..500001]of longint;
  f:array[0..500001]of int64;
  n,m,k,i,l,r,mid,ans:longint;
function check(z:longint):boolean; 
var
  zz,h,t,i,j:longint;
begin
  h:=1;t:=1;
  q[1]:=0;
  f[0]:=0;
  for i:=1 to n do f[i]:=-1000000000;
  zz:=0;
  for i:=1 to n do 
    begin 
      while (x[i]-x[zz]>k+z)and(zz<=i) do inc(zz);
      while (zz<i)and(x[i]-x[zz]>=k-z)and(x[i]-x[zz]<=k+z) do 
        begin 
          while (f[zz]>f[q[t]])and(h<=t) do dec(t);
          inc(t);
          q[t]:=zz;
          inc(zz);
        end;
      while (x[i]-x[q[h]]>k+z)and(h<=t) do inc(h);//维护单调队列
      if (h<=t)and(x[i]-x[q[h]]>=k-z)and(x[i]-x[q[h]]<=k+z) then f[i]:=f[q[h]]+a[i];
      if f[i]>=m then exit(true);
    end;//dp
  exit(false);
end;
begin
  readln(n,k,m);
  for i:=1 to n do readln(x[i],a[i]);
  l:=0;
  r:=x[n];
  ans:=-1;
  while l<=r do 
    begin
      mid:=(l+r) >> 1;
      if check(mid) then begin ans:=mid;r:=mid-1 end
        else l:=mid+1;
    end;//二分答案
  writeln(ans);
end.