每个点只能从时间，b+a，b-a三维都不大于它的点转移过来，将点按时间分成尽量少的一些段，每段内三维同时非严格单调，每段内的点可能因为连续选一段而产生平方的贡献，可以每段开一个单调栈维护斜率优化dp处理。
注意到b-a和b+a同时小于可以推出时间小于，因此可以按b-a升序处理，b+a一维用树状数组维护前缀最值，处理选的点在时间上不连续的情况。
#include<bits/stdc++.h> typedef long long i64; const int N=5e5+7; int _(){ int x=0,c=getchar(); while(c<48)c=getchar(); while(c>47)x=x*10+c-48,c=getchar(); return x; } int n,xs[N],xp=0,idp=0; i64 f[N],bit[N],ans=0; void maxs(i64&a,i64 b){if(a<b)a=b;} void ins(int x,i64 y){ for(;x<=xp;x+=x&-x)maxs(bit[x],y); } i64 sum(int x){ i64 y=0; for(;x;x-=x&-x)maxs(y,bit[x]); return y; } i64 F(int x){ return f[x]+i64(x)*x; } int mem[N],*mp=mem; struct mq{ int*q,p; void init(int sz){ q=mp,mp+=sz; p=-1; } void upd(int i){ int K=2*i+2; while(p>0){ int a=q[p],b=q[p-1]; if(F(b)-F(a)>=K*i64(b-a))--p; else break; } if(p>=0){ int w=q[p],d=i+1-w; maxs(f[i],f[w]+i64(d)*d-1); } while(p>0){ int a=q[p-1],b=q[p]; i64 Fb=F(b); if((Fb-F(a))*(i-b)<=(F(i)-Fb)*(b-a))--p; else break; } q[++p]=i; } }qs[N]; struct pos{ int x,y,id,tp; void init(int a,int b,int c){ xs[++xp]=x=a; y=b; id=c; } void upd(){ f[id]=1+sum(x); qs[tp].upd(id); ins(x,f[id]); } bool operator<(const pos&p)const{ return y<p.y||y==p.y&&x<p.x; } bool operator<=(const pos&p)const{ return x<=p.x&&y<=p.y; } }ps[N]; int main(){ n=_(); for(int i=1;i<=n;++i){ int a=_(),b=_(); ps[i].init(b+a,b-a,i); } for(int i=1,j=1;i<=n;i=j){ for(++j;j<=n&&ps[j-1]<=ps[j];++j); for(qs[++idp].init(j-i);i<j;ps[i++].tp=idp); } std::sort(xs+1,xs+xp+1); for(int i=1;i<=n;++i){ ps[i].x=std::lower_bound(xs+1,xs+xp+1,ps[i].x)-xs; } std::sort(ps+1,ps+n+1); for(int i=1;i<=n;++i)ps[i].upd(); for(int i=1;i<=n;++i)maxs(ans,f[i]); printf("%lld ",ans); return 0; }