Cod sursă (job #143268)

// Tabăra de pregătire a Lotului Național - Sovata 2014
// © 2014 Dragoș Vasile Oprică

#include <cassert>
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;

#define x first.first
#define y first.second
#define z second.first
#define t second.second

const int NMAX = 2050;
ifstream fin("canibali.in");
ofstream fout("canibali.out");

vector<pair<pair<int, int>, pair<int, int> > > V(NMAX);
vector<int> G[NMAX << 1], L(NMAX << 1, -1), R(NMAX, -1);
bitset<NMAX << 1> vis;
int N, paired;

inline bool canEat(int eater, int eaten) {
	return (V[eater].x >= V[eaten].x && V[eater].y >= V[eaten].y && V[eater].z >= V[eaten].z && V[eater].t > V[eaten].t);
}

inline bool canEatMutual(int eater, int eaten) {
	return (V[eater].x == V[eaten].x && V[eater].y == V[eaten].y && V[eater].z == V[eaten].z && V[eater].t == V[eaten].t);
}

inline bool pairUp(int node) {
	if (vis[node])
		return false;
	vis[node] = true;

	for (vector<int>::iterator i = G[node].begin(); i != G[node].end(); ++i)
		if (R[*i] == -1) {
			L[node] = *i;
			R[*i] = node;
			return true;
		}
	for (vector<int>::iterator i = G[node].begin(); i != G[node].end(); ++i)
		if (pairUp(R[*i])) {
			L[node] = *i;
			R[*i] = node;
			return true;
		}

    return 0;
}

int main() {
	fin >> N;
	assert(1 <= N && N <= 2048);
	for (int i = 0; i < N; ++i) {
		fin >> V[i].x >> V[i].y >> V[i].z >> V[i].t;
		assert(0 <= V[i].x && V[i].x <= 131072);
		assert(0 <= V[i].y && V[i].y <= 131072);
		assert(0 <= V[i].z && V[i].z <= 131072);
		assert(0 <= V[i].t && V[i].t <= 131072);
	}

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j)
			if (canEatMutual(i, j)) {
				if (i < j) {
					G[i].push_back(j);
					G[i + N].push_back(j);
				}
			}
			else if (canEat(i, j)) {
				G[i].push_back(j);
				G[i + N].push_back(j);
			}
	}

	bool done;
	do {
		done = true;
		vis.reset();
		for (int i = 0; i < (N << 1); ++i)
			if (L[i] < 0 && pairUp(i)) {
				done = false;
				++paired;
			}
	}
	while (!done);
	fout << N - paired << "\n";

	return 0;
}