Cod sursa(job #2478667)

Utilizator ivddabDabelea Ioana-Viviana ivddab Data 22 octombrie 2019 15:34:29
Problema Cutii Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#define NM 3503
using namespace std;
ifstream f("cutii.in");
ofstream g("cutii.out");
int n,t,st,dr,i,mijl,lg;
int r[NM];
struct cutie{
   int x,y,z;
};
cutie a[NM];
bool cmp( cutie c, cutie d ){
  if(c.x==d.x){
     if(c.y==d.y) return c.z<d.z;
       else       return c.y<d.y;
  }
  return c.x<d.x;
}
bool comp( cutie c, cutie d ){
  if(c.x<=d.x&&c.y<=d.y&&c.z<=d.z) return 1;
  return 0;
}
int main()
{
    f>>n>>t;
    while(t!=0){ t--;
        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=1;i<=n;i++) g<<a[i].x<<' '<<a[i].y<<' '<<a[i].z<<'\n';
//        g<<'\n';
        lg=0;
        memset(r,0,sizeof(r));
        for(i=1;i<=n;i++){
            st=1; dr=lg;
            while(st<=dr){
                mijl=(st+dr)/2;
                //g<<r[mijl]<<' '<<i<<' '<<comp(a[r[mijl]],a[i])<<'\n';
                if(comp(a[r[mijl]],a[i])==1) st=mijl+1;
                   else                     dr=mijl-1;
            }
            r[st]=i; lg=max(lg,st);
        }
        g<<lg<<'\n';
    }
    return 0;
}