Cod sursa(job #40824)
#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;
}