Cod sursa(job #40824)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 27 martie 2007 19:24:07
Problema Cutii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>
#define fin  "cutii.in"
#define fout "cutii.out"
#define Nmax 3501

struct box {
	int X; int Y; int Z;
};

int T,N;
box v[Nmax];

void qsort(int st,int dr) {
int i,j,m;
box aux;
	i=st; j=dr;
	m=v[(i+j)/2].X;
	do {
		while (v[i].X>m) ++i;
		while (v[j].X<m) --j;
		if (i<=j) {
			aux=v[i]; v[i]=v[j]; v[j]=aux;
			++i; --j;
		}
	} while (i<j);
	if (i<dr) qsort(i,dr);
	if (j>st) qsort(st,j);
}

int main() {
int i,j,k,max,ret,best[Nmax];

	freopen(fin,"r",stdin); freopen(fout,"w",stdout);

	scanf("%i%i",&N,&T);

	for (k=1;k<=T;++k) {
		
		for (i=1;i<=N;++i) 
			scanf("%i%i%i",&v[i].X,&v[i].Y,&v[i].Z);
		qsort(1,N);
		ret=0;
		for (i=1;i<=N;++i) {
			max=0;
			for (j=1;j<i;++j) 
				if (v[j].Y>v[i].Y && v[j].Z>v[i].Z && best[j]>max) 
					max=best[j];
			best[i]=max+1;
			if (best[i]>ret) 
				ret=best[i];
		}
		printf("%i\n",ret);
	}

	fclose(stdin); fclose(stdout);
	return 0;
}