1 solutions
-
0
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