sum= A*h+B*s排序
然后枚举height和speed的最小值
然后用两个指针:先枚举speed最小值,然后一边枚举v的最小值一边查询符合条件的人数。
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std; typedef long long LL; #define N 10010 struct data
{
LL h,s,sum;
}x[N],y[N]; LL n,A,B,C;
LL minn,maxn;
LL ans,cnt,l,r; LL getLL()
{
LL x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
} LL cmp1(const data &a,const data &b)
{
return a.h<b.h;
} LL cmp2(const data &a,const data &b)
{
return a.sum<b.sum;
} bool check1(LL p)
{
return y[p].s<=maxn && y[p].s>=minn;
} bool check2(LL p)
{
return x[p].s<=maxn && x[p].s>=minn;
} int main()
{
n=getLL(),A=getLL(),B=getLL(),C=getLL();
for (LL i=1;i<=n;i++)
{
x[i].h=getLL();
x[i].s=getLL();
x[i].sum=A*x[i].h+B*x[i].s;
y[i]=x[i]; }
sort(x+1,x+n+1,cmp1);
sort(y+1,y+n+1,cmp2);
for (LL i=1;i<=n;i++)
{
minn=x[i].s;
maxn=minn+C/B;
l=r=cnt=0;
for (LL j=1;j<=n;j++)
{
while (r<n && y[r+1].sum<=A*x[j].h+B*x[i].s+C)
r++,cnt+=check1(r);
while (l<n && x[l+1].h<x[j].h)
l++,cnt-=check2(l);
ans=max(ans,cnt);
}
}
printf("%lld\n",ans);
return 0;
}