Cod sursa(job #77481)

Utilizator a7893Nae Mihai a7893 Data 14 august 2007 13:59:59
Problema Cutii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<stdio.h>
#include<stdlib.h>
#define N 350000
int n,t,s[N],k;
struct vec{
	int x,y,z,vol;
}v[N];
int maxim(const void *a, const void *b)
{
	vec *aa,*bb;
	aa=(vec*)a;
	bb=(vec*)b;
	return aa->x-bb->x;
}
int search(int x,int y)
{
	/*int p,u,m;
	p=0;
	u=k-1;
	m=(p+u)/2;
	while(p<u)
	{
		if(x>s[m])
			p=m+1;
		else
			u=m;
		m=(p+u)/2;
	}
	return m;*/
	int i;
	for(i=0;i<k;i++)
		if(s[i]>=x&&s[i]>y)
			return i;
	return k++;
}
void read_solve()
{
	int i1,i,poz;
	scanf("%d%d",&n,&t);
	for(i1=0;i1<t;i1++)
	{
		k=0;
		for(i=0;i<n;i++)
		{
			scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].z);
			v[i].vol=v[i].x*v[i].y*v[i].z;
		}
		qsort(v,n,sizeof(v[0]),maxim);
		s[k++]=v[0].vol;
		for(i=1;i<n;i++)
		{
			poz=search(v[i].y,v[i].z);
			s[poz]=v[i].x*v[i].y;
		}
		printf("%d\n",k);
	}
}
int main()
{
	freopen("cutii.in","r",stdin);
	freopen("cutii.out","w",stdout);
	read_solve();
	return 0;
}