Rezultati

Up. imeNalogaJezikRezultatČas oddaje
pspace-2017 Škatle C++ 100/100OK 20. apr '17 @ 17:51

Test Točke Porabljen spomin Porabljen čas Status
#1 6/6 3,082 MiB 0,004 s OK
#2 6/6 3,094 MiB 0,004 s OK
#3 6/6 3,113 MiB 0,004 s OK
#4 6/6 3,113 MiB 0,004 s OK
#5 6/6 3,078 MiB 0,004 s OK
#6 7/7 3,082 MiB 0,004 s OK
#7 7/7 3,117 MiB 0,004 s OK
#8 7/7 3,109 MiB 0,004 s OK
#9 7/7 3,082 MiB 0,004 s OK
#10 7/7 3,117 MiB 0,004 s OK
#11 7/7 3,086 MiB 0,004 s OK
#12 7/7 3,098 MiB 0,004 s OK
#13 7/7 3,137 MiB 0,010 s OK
#14 7/7 3,156 MiB 0,004 s OK
#15 7/7 3,137 MiB 0,004 s OK

Ocenjevani program (main.cpp):
#include <bits/stdc++.h>

using namespace std;

const int N = 108;
vector<int> boxes[N];
int n, d;

bool conn[N][N];
int cache[N];
vector<int> children[N];

int dfs(int x) {
    if(cache[x] != -1) return cache[x];

    int r = 1;
    for(int j : children[x]) {
        if(conn[x][j]) {
            r = max(r, 1+dfs(j));
        }
    }

    cache[x] = r;
    return r;
}

bool comp(const vector<int>& b1, const vector<int>& b2) {
    int n = b1.size();
    for(int i=0;i<n;i++) {
        if(b1[i]>= b2[i]) return false;
    }
    return true;
}

int main() {
    cin >>n >>d;

    for(int i=0;i<n;i++) {
       for(int j=0;j<d;j++) {
           int x;
           cin>>x;
           boxes[i].push_back(x);
           sort(boxes[i].begin(), boxes[i].end());
       }
    }

    for(int i=0;i<n;i++) {

        /*cout << "children of ";
        for(int j=0;j<d;j++) {
            cout <<boxes[i][j] << " ";
        }
        cout << endl;*/

        for(int j=0;j<n;j++) {
            conn[i][j] = comp(boxes[j], boxes[i]);
            if(conn[i][j]) {
                children[i].push_back(j);
                /*for(int k=0;k<d;k++) {
                    cout <<boxes[j][k] << " ";
                }
                cout <<endl;*/
            }
        }
    }

    memset(cache, -1, sizeof(cache));

    int res = 0;
    for(int i=0;i<n;i++) {
        int dd = dfs(i);
        if(dd > res) {
            res = dd;
        }
    }

    cout << res <<endl;

    return 0;
}