Cod sursa(job #2413428)

Utilizator Chirita_MateiChirita Matei Chirita_Matei Data 23 aprilie 2019 13:23:10
Problema Cutii Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <bits/stdc++.h>

#pragma region TEMPLATE

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef std::pair<int, int> pii;

#define dbg(x) cerr<<#x": "<<(x)<<'\n'
#define dbg_p(x) cerr<<#x": "<<(x).first<<' '<<(x).second<<'\n'
#define dbg_v(x, n) {cerr<<#x"[]: ";for(long long =0;_<n;++)cerr<<(x)[_]<<' ';cerr<<'\n';}
#define all(v) v.begin(), v.end()
#define fs first
#define sc second
#define pb push_back
#define oo 2000000010
#define MOD2 666013
#define MOD 1000000007
#define ST_SIZE 1048600
#define QMAX
#define PI 3.14159265359
#define zeros(x) (x^(x-1)&x) // x&(-x)
#define NMAX 100010
#define MMAX 100010

using namespace std;

template<typename T1, typename T2>
ostream& operator <<(ostream &out, const pair<T1, T2> &item) {
	out << '(' << item.first << ", " << item.second << ')';
	return out;
}

template<typename T>
ostream& operator <<(ostream &out, const vector<T> &v) {
	for(const auto &item : v) out << item << ' ';
	return out;
}


#pragma endregion

using namespace std;
ofstream fout("cutii.out");
ifstream fin("cutii.in");

struct Box{
    int x;
    int y;
    int z;
};


Box v[3510];
int n, t;
int aib[3510][3510];

void update(int x, int y, int val){
    for(int i = x; i <= n; i += zeros(i)){
        for(int j = y; j <= n; j += zeros(j)){
            aib[i][j] = max(val, aib[i][j]);
        }
    }
}

int maxF(int x, int y){
    int sol = -1;
    for(int i = x; i >= 1; i -= zeros(i)){
        for(int j = y; j >= 1; j -= zeros(j)){
            sol = max(sol, aib[i][j]);
        }
    }

    return sol;
}

void reset(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            aib[i][j] = 0;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin >> n >> t;

    while(t--){
        for(int i = 1; i <= n; i++){
            fin >> v[i].x >> v[i].y >> v[i].z;
        }

        sort(v + 1, v + 1 + n, [&](Box a, Box b){
            return a.z < b.z;
        });

        int ans = 1;

        for(int i = 1; i <= n; i++){
            int sol = maxF(v[i].x, v[i].y);
            update(v[i].x, v[i].y, sol + 1);

            ans = max(ans, sol + 1);
        }

        reset();

        fout << ans << '\n';
    }

    return 0;
}