Cod sursa(job #2433206)

Utilizator bluestorm57Vasile T bluestorm57 Data 26 iunie 2019 12:14:34
Problema Cutii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 3510;
struct cutie{
    int x,y,z;
}v[NMAX];
int n,t,best[NMAX],dp[NMAX][NMAX];

bool cmp(const cutie &X, const cutie &Y){
    return X.x < Y.x;
}

int query(int y, int z){
    int maxim = 0,i,j;
    for(i = y ; i; i -= (i & (-i)))
        for(j = z ; j ; j -= (j & (-j)))
            maxim = max(maxim, dp[i][j]);
    return maxim;
}

void update(int y, int z, int val){
    int i,j;
    for(i = y ; i <= n ; i += (i & (-i)))
        for(j = z ; j <= n ; j += (j & (-j)))
            dp[i][j] = max(dp[i][j], val);

}

void Delete(int y, int z){
    int i,j;
    for(i = y ; i <= n ; i += (i & (-i)))
        for(j = z ; j <= n ; j += (j & (-j)))
            dp[i][j] = 0;
}

int main(){
    int i;
    f >> n >> t;
    while(t){
        for(i = 1 ; i <= n ; i++)
            f >> v[i].x >> v[i].y >> v[i].z;
        sort(v + 1, v + n + 1, cmp);
        int ans = 0;
        for(i = 1 ; i <= n ; i++){
            best[i] = query(v[i].y, v[i].z) + 1;
            update(v[i].y, v[i].z, best[i]);
            ans = max(ans, best[i]);
        }
        g << ans << "\n";
        for(i = 1 ; i <= n ; i++)
            Delete(v[i].y, v[i].z);

        t--;
    }


    return 0;
}