4134866_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

using namespace std;

int w[1000];
struct node
{
	int w, h, t;

	bool operator < (const node &that)	const
	{
		return this->t < that.t;
	}
}c[1000];

int cnt[10000];

int main()
{
	int n, i, j;
	int A, B, C;

	scanf("%d%d%d%d", &n, &A, &B, &C);
	memset(cnt, 0, sizeof cnt);
	for (i = 0; i < n; i++)
	{
		scanf("%d%d", &c[i].h, &c[i].w);
		c[i].t = A * c[i].h + B * c[i].w;
		w[i] = c[i].w;
		//cnt[w[i]]++;
	}
	sort(w, w + n);
	sort(c, c + n);
	int ans = 0;
	for (i = 0; i < n; i++)
	{
		int tmp = 0;
		int last = 0;
		int bak = 0;
		for (j = 0; j < n; j++)
		{
			int tot = C + A * c[i].h + B * w[j];
			while (last < n && c[last].t <= tot)
			{
				if (c[last].h >= c[i].h && c[last].w >= w[j])
				{
					tmp++;
					if (c[last].w == w[j])
					{
						cnt[w[j]]++;
					}
				}
				last++;
			}
			if (tmp > ans)
			{
				ans = tmp;
			}
			tmp -= cnt[w[j]];
		}
	}
	printf("%d\n", ans);
	return 0;
}