4135108_ac_141ms_728k.cc

北大大牛代码 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[1000];
int id[100000];

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

	scanf("%d%d%d%d", &n, &A, &B, &C);
	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;
	}
	sort(w, w + n);
	int tt = 0;
	id[w[0]] = 0;
	for (i = 1; i < n; i++)
	{
		if (w[i] != w[i - 1])
			id[w[i]] = ++tt;
	}
	sort(c, c + n);
	int ans = 0;
	for (i = 0; i < n; i++)
	{
		if (i && c[i].h == c[i - 1].h)
			continue;
		int tmp = 0;
		int last = 0;
		memset(cnt, 0, sizeof cnt);
		for (j = 0; j < n; j++)
		{
			if (j && w[j] == w[j - 1])
				continue;
			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++;
					cnt[id[c[last].w]]++;
				}
				last++;
			}
			if (tmp > ans)
			{
				ans = tmp;
			}
			tmp -= cnt[id[w[j]]];
		}
	}
	printf("%d\n", ans);
	return 0;
}