[1日のテーマにこだわる==]団結したチーム

【説明】
n人がいて、今年のnoiに対処するために「沖金」チームを構成する必要があります.沖金の人数は多ければ多いほどいいですが、もちろん、一定の条件を満たす必要があります.一人一人に2つの説明があります:h身長、w体重.関数Fi=A*(Hi-h)+B*(Wi-w)を定義し、Hi,Wiはi番目の個人の身長と体重を表し、h,wは選択したチームの最小身長と最小体重を表し、A,Bは与えられた定数である.現在、学校の指導者の要求は1つのチームを見つけて、すべてのチームの中の人のfi値を満たしてCを超えないで、しかもこの条件の上でチームの最大の可能な人数を見つけます.
【入力形式】
1行目の個数N
2行目の3つの数A,B,C
次のN行、行ごとに2つの数Hi,Wi
【出力形式】
1行だけで、チームの最大可能な人数です.
【サンプル入力】
8
 1 2 4
 5 1
 3 2
 2 3
2 1
7 2
6 4
5 1
4 3
【サンプル出力】
5
【データ範囲】
N<=1000; A,B,C<=10000; Hi,Wi<=100000;
【分析】
前処理he[i]はa*h[i]+b*w[i]である.
まず、私たちはすべての人をhに従ってソートし、nから1までhが一番小さい人を列挙します.現在列挙されているiのhはi~nの中で最も小さいので、iを含むチームはi~nの中で選択されるに違いない.では、私たちがしなければならないのは、どの人のw[i]が一番小さいかを見ることです.私たちのiは必ず取らなければならないので、i~nをwに並べ替えると、最もwの人のw値はiより小さいに違いありません.では、w[i]より小さい人を列挙するだけでいいです.最小のhは決定的である(h[i])ため、he 1がhe-a*hを表すことを先に計算することができ、それからw値がiを超えない人を列挙し、he 1を大きな根の山に維持し、最大の満足が計算された数がcより小さい場合、彼より小さい肯定も満足する.注意しなければならないのは、iは必要な人です.では、he 1値が最大でiであり、現在列挙されているのは点jであり、関数値がcより大きい場合、w値がjより小さい人もだめに違いない.wがjより小さい人が最もwが最小の人が存在すると、関数値はjが最も最小の人が存在するときよりも大きくなるに違いないからだ.(話が混乱している).
そして私たちはそうすればいい!1つのソート、1つのスタック.

#include <stdio.h>

#define maxn 2010



int h[maxn],w[maxn],he[maxn],w1[maxn],he1[maxn],heep[maxn];

int i,j,k,n,m,s,max,a,b,c,t,top;



void init()

{

     scanf("%d%d%d%d",&n,&a,&b,&c);

     for (i=1;i<=n;++i) scanf("%d%d",&h[i],&w[i]);

}



void swap(int &a,int &b)

{

     int k;

     k=a; a=b; b=k;

}



void sort(int l,int r,int a[],int b[])

{

     int i,j,k;

     i=l; j=r; k=a[(l+r)>>1];

     while (i<j)

     {

           while (a[i]<k) ++i;

           while (a[j]>k) --j;

           if (i<=j)

           {

                    swap(a[i],a[j]);

                    swap(b[i],b[j]);

                    ++i;

                    --j;

           }

     }

     if (l<j) sort(l,j,a,b);

     if (i<r) sort(i,r,a,b);

}



void insert(int p)

{

     heep[++top]=p;

     p=top;

     while ((p>1)&&(he1[heep[p]]>he1[heep[p/2]]))

     {

           swap(heep[p],heep[p/2]);

           p/=2;

     }

}



void dele()

{

     int p;

     heep[1]=heep[top];

     --top;

     p=1;

     while (((p*2<=top)and(he1[heep[p*2]]>he1[heep[p]]))or

              ((p*2+1<=top)and(he1[heep[p*2+1]]>he1[heep[p]])))

     {

          if (p*2+1<=top)

           if (he1[heep[p*2]]>he1[heep[p*2+1]])

            { swap(heep[p],heep[p*2]); p=p*2; } else

            { swap(heep[p],heep[p*2+1]); p=p*2+1; } else

            { swap(heep[p],heep[p*2]); p=p*2; }

         }

}



void work()

{

     sort(1,n,h,w);

     max=0;

     for (i=1;i<=n;++i) he[i]=a*h[i]+b*w[i];

     for (i=n;i>0;--i)

     {

         t=0;

         for (j=n;j>=i;--j)

         {

             w1[++t]=w[j];

             he1[t]=he[j]-a*h[i];

         }

         sort(1,t,w1,he1);

         for (j=t;j>=1;--j) 

             if (w1[j]==w[i])

             {

                             k=j;

                             break;

             }

         s=top=0;

         int tt=0;

         for (j=t;j>=k;--j)

             if (he1[j]-b*w1[k]<=c) insert(j);

         if (top>max) max=top;

         for (j=k-1;j>=1;--j)

         {

             while ((he1[heep[1]]-b*w1[j]>c)&&(top>0))

             {

                   if (heep[1]==t)

                   {

                                  tt=1;

                                  break;

                   }

                   dele();

             }

             if (tt) break;

            if (he1[j]-b*w1[j]<=c) insert(j);

            if (top>max) max=top;

         }

     }

}



int main()

{

    freopen("team.in","r",stdin);

    freopen("team.out","w",stdout);

    

    init();

    work();

    printf("%d
",max);

    return 0;

}