Cod sursă (job #435534)

#include <fstream>
#include <vector>

using namespace std;

ifstream fin("canibali.in");
ofstream fout("canibali.out");

const int VAL=7005;

struct CANIBAL
{
    int X, Y, Z, T;
};

CANIBAL C[VAL];

int N, i, j, ANS;
int L[VAL], R[VAL];
bool nemodif, tried[VAL];
vector <int> G[VAL];

bool CMP(CANIBAL A, CANIBAL B)
{
    int nr=0;
    if (A.X>=B.X)
        nr++;
    if (A.Y>=B.Y)
        nr++;
    if (A.Z>=B.Z)
        nr++;
    if (A.T>=B.T)
        nr++;
    return nr==4;
}

bool PairUp(int nod)
{
    if (tried[nod]==true)
        return false;
    tried[nod]=true;
    vector <int> :: iterator it;
    for (it=G[nod].begin(); it!=G[nod].end(); it++)
    {
        if (L[*it]==0)
        {
            R[nod]=*it;
            L[*it]=nod;
            return true;
        }
    }
    for (it=G[nod].begin(); it!=G[nod].end(); it++)
    {
        if (PairUp(L[*it])==true)
        {
            R[nod]=*it;
            L[*it]=nod;
            return true;
        }
    }
    return false;
}

int main()
{
    fin >> N;
    for (i=1; i<=N; i++)
        fin >> C[i].X >> C[i].Y >> C[i].Z >> C[i].T;
    for (i=1; i<=N; i++)
    {
        for (j=1; j<=N; j++)
        {
            if (i==j)
                continue;
            if (CMP(C[i], C[j])==true)
            {
                if (C[i].X==C[j].X && C[i].Y==C[j].Y && C[i].Z==C[j].Z && C[i].T==C[j].T && j<i)
                    continue;
                G[i].push_back(j);
                G[N+i].push_back(j);
            }
        }
    }
    while (nemodif==false)
    {
        nemodif=true;
        for (i=1; i<=2*N; i++)
            tried[i]=false;
        for (i=1; i<=2*N; i++)
            if (PairUp(i)==true)
                nemodif=false;
    }
    for (i=1; i<=N; i++)
        if (L[i]>0)
            ANS++;
    fout << N-ANS << '\n';
    fin.close();
    fout.close();
    return 0;
}