P4165 [SCOI2007] 组队 详解

10 6 6 40
7 9
6 9
5 7
7 4
5 3
9 1
10 3
4 5
8 9
6 5

6

//# pragma GCC optimize("Ofast")
# include <bits/stdc++.h>
# define fr front
# define il inline
# define fir first
# define sec second
# define vec vector
# define it iterator
# define pb push_back
# define lb lower_bound
# define ub upper_bound
# define all(x) x.begin(), x.end()
# define mem(a, b) memset(a, b, sizeof(a))

# define lc (t[p].l)
# define rc (t[p].r)
# define ls(x) (x << 1)
# define rs(x) (x << 1 | 1)
# define lson ls(p), l, mid
# define rson rs(p), mid + 1, r

# define sqr(x) ((x) * (x))
# define bpc __builtin_popcount
# define lowbit(x) ((x) & (-(x)))
# define geti(x, i) (((x) >> (i)) & 1)
# define set1(x, i) ((x) | (1 << (i)))
# define set0(x, i) ((x) & (~(1 << (i))))

# define debug1(x) cerr << #x << " = " << x << " "
# define debug2(x) cerr << #x << " = " << x << "\n"
# define bug cerr << "--------------------------\n"

# define each1(i, x) for(auto (i) : (x))
# define each2(i, x) for(auto (&i) : (x))
# define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
# define pre(i, a, b) for(int i = (a); i >= (b); -- i)
# define G(i, h, u, ne) for(int i = (h[(u)]); i; i = (ne[(i)]))
# define reps(i, a, b, c) for(int i = (a); i <= (b); i += (c))
# define pres(i, a, b, c) for(int i = (a); i >= (b); i -= (c))
using namespace std;

using DB = double;
using LL = long long;
using LDB = long double;
using PII = pair<int, int>;
using ULL = unsigned long long;

const int N = 5e3 + 10, V = 1e4 + 10;
const int INF1 = 0x3f3f3f3f, INF2 = INT_MAX;
const LL INF3 = (LL)1e18, INF4 = 0x3f3f3f3f3f3f3f3f, INF5 = LLONG_MAX;

int n, a, b, c, sum, ans;
int h[N], v[N], pre[V];

vec<int> val;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> n >> a >> b >> c;
	
	rep(i, 1, n){
		cin >> h[i] >> v[i];
		val.pb(h[i]);
	}
	
	sort(all(val));
	val.erase(unique(all(val)), val.end()); 
	
	each2(H, val){//去重枚举可以将10000降到5000，而且确实应该用存在的h 
		sum = 0;
		mem(pre, 0);
		
		rep(i, 1, n){
			if(H > h[i]) continue;//很明显 
			int d = ceil((DB)(a * (h[i] - H) + b * v[i] - c) / (DB)b);
			if(d > v[i]) continue;//根本没有合法区间 
			if(d < 0) d = 0;//看下面的输出调试，注意越界 
			pre[d] ++;
			pre[v[i] + 1] --;
//			cout << d << " " << v[i] + 1 << "\n";
		}
		
		rep(i, 1, 10000) pre[i] += pre[i - 1];
		rep(i, 1, n) ans = max(ans, pre[v[i]]);//只能是存在的v 
	}
	
	cout << ans;
	
	return 0;
}