1 solutions

  • 0
    @ 2025-11-5 16:32:19

    C++ :

    /*
    	author :hzoi_ztx
    	title  :cogs 25482:Beauty
    	ALG    :单调队列
    	CMT    :枚举每个 H ,且使之为最小的 H , 再单调枚举 W ,
    			则得到了当前的最小 H 与各个 W 值组合时的 ans
    
    	[2014 10 27]
    */
    
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    
    #define  maxn  1005
    #define  Size  1005
    
    struct tx{
    	int f , H , W , id ;
    	bool operator < (const tx & b) const { return f < b.f ; }
    } a[maxn] , b[maxn] ;
    
    bool cmp(const tx a,const tx b) {
    	if (a.W == b.W) return a.H < b.H;
    	else return a.W < b.W ;
    }
    /*
    struct monque{
    	int q[Size] , head , rear ;
    	int h ;
    	int lim ;
    	inline void clear()	{ head = 0 ; rear = -1 ; }
    	inline bool empty()	{ return head > rear ; }
    	inline int front()	{ return q[head] ; }
    	inline int back()	{ return q[rear] ; }
    	inline int cnt()    { return rear-head+1 ; }
    	inline void pop_front() { head ++ ; }
    	inline void pop_back()  { rear -- ; }
    	inline void push_back(int x) { q[++head] = x ; } ;
    	inline void push(int x) {
    	}
    } q ;*/
    
    int n , A , B , C , ans = 0 ;
    int h , w , v ;
    int flag[maxn] ;
    
    int main() {
    //	#define READ
    	#ifdef  READ
    	    freopen("beauty.in" ,"r",stdin ) ;
    	    freopen("beauty.out","w",stdout) ;
    	#endif
    	int i , j , k , now ;
    	scanf("%d%d%d%d", &n , &A , &B , &C ) ;
    	for (i = 1 ; i <= n ; i ++ ) {
    		scanf("%d%d", &b[i].H , &b[i].W ) ;
    	}
    	std::sort(b+1 , b+n+1 , cmp) ;
    	for (i = 1 ; i <= n ; i ++ ) {
    		a[i] = b[i] ; a[i].id = i ;
    		a[i].f = a[i].H*A+a[i].W*B-C ;
    	}
    	std::sort(a+1 , a+n+1) ;
    	for (i = 1 ; i <= n ; i ++ ) {
    		k = 1 ; now = 0 ;
    		memset(flag , 0 , sizeof (flag)) ;
    		for (j = 1 ; j <= n ; j ++ ) {
    			v = b[i].H*A+b[j].W*B ;
    			while (k<=n && a[k].f<=v) {
    				if (a[k].H>=b[i].H && a[k].W>=b[j].W) {
    					now ++ ; flag[a[k].id] ++ ;
    				}
    				k ++ ;
    			}
    			if (now > ans) ans = now ;
    			now -= flag[j] ;
    		}
    	}
    	printf("%d\n", ans ) ;
    	#ifdef  READ
    	    fclose(stdin ) ;
    	    fclose(stdout) ;
    	#else
    	    getchar() ; getchar() ;
    	#endif
    	return 0 ;
    }
    
    • 1

    Information

    ID
    17837
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By