Cod sursa(job #1200657)

Utilizator tudi98Cozma Tudor tudi98 Data 23 iunie 2014 11:55:47
Problema Cutii Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
#define dim 10505

struct D{int x,y,z;};

inline bool comp(D a,D b){
	return a.x < b.x;
}

D a[dim];
int best[dim];

int main(){
	
	ifstream f("cutii.in");
	ofstream g("cutii.out");

	int n,t,i,j;
	f >> n >> t;
	while(t--){
		int BestC=0;
		for(i=1;i<=n;i++) best[i]=0;
		for(i=1;i<=n;i++)
			f >> a[i].x >> a[i].y >> a[i].z;
		sort(a+1,a+n+1,comp);
		for(i=n-1;i>=1;i--){
			if(a[i].x==n || a[i].y==n || a[i].z==n) continue;
			for(j=n;j>i;j--){
				if(a[j].y>a[i].y && a[j].z>a[i].z && best[i]<best[j]+1){
					best[i]=best[j]+1;
				}
			}
			BestC=max(BestC,best[i]);
		}
		g << BestC+1 << "\n";
	} 
}