Cod sursa(job #2503160)

Utilizator radugnnGone Radu Mihnea radugnn Data 2 decembrie 2019 16:42:18
Problema Cutii Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cutii.in");
ofstream fout("cutii.out");
int N,D[3510],stt,dim,i,T;
struct cutie{
    int a;
    int b;
    int c;
}v[3510];
bool cmp(cutie x, cutie y){
    if(x.a < y.a && x.b < y.b && x.c < y.c)
        return 1;
    return 0;
}
bool cmp2(cutie x, cutie y){
    return x.a<y.a;
}
int cautare (int x){
    int st=1;
    int dr=dim;
    while(st<=dr){
    int mid=(st+dr)/2;
        if(cmp(v[D[mid]],v[x]))
            st=mid+1;
        else
            dr=mid-1;
    }
    return st;
}
int main(){
    fin>>N>>T;
    while(T--){
    for(i=1;i<=N;i++){
        fin>>v[i].a>>v[i].b>>v[i].c;
    }
    sort(v+1,v+N+1,cmp2);
    D[1]=1;
    dim=1;
    for(i=2;i<=N;i++){
        stt=cautare(i);
        if(stt>dim)
            D[++dim]=i;
        else
            D[stt]=i;
    }
    fout<<dim<<"\n";
    }
    return 0;
}