Cod sursa(job #73689)

Utilizator andrei.12Andrei Parvu andrei.12 Data 20 iulie 2007 13:42:03
Problema Cutii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<cstdio>
#include<cstdlib>
int l[5000], max;
struct cutie{
	int a, b, c;
};
cutie v[3505];
int comp(const void*x, const void*y){
	cutie xx=*(cutie*)x, yy=*(cutie*)y;
	if (xx.a<yy.a) return -1;
	if (xx.a>yy.a) return 1;
	return 0;
}
int main()
{
	freopen("cutii.in","r",stdin);
	freopen("cutii.out","w",stdout);
	int n, t, nrt, i, k, ;
	scanf("%d%d", &n, &t);
	for (nrt=1; nrt<=t; nrt++){
		for (i=1; i<=n; i++)
			scanf("%d%d%d", &v[i].a, &v[i].b, &v[i].c);
		qsort(v, n+1, sizeof(v[0]), comp);
		for (i=1; i<=n; i++)
			l[i] = 0;
		l[n] = 1;
		for (k=n-1; k>=1; k--)
		{
			max = 0;
			for (i=k+1; i<=n; i++)
				if (v[i].b >= v[k].b && v[i].c >= v[k].c && l[i] > max)
					max = l[i];
			l[k] = 1+max;
		}
		max = l[1];
		for (k=1; k<=n; k++)
			if (l[k] > max)
				max = l[k];
		printf("%d\n", max);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}