Submission #1326776

#TimeUsernameProblemLanguageResultExecution timeMemory
1326776DeathIsAweOlympiads (BOI19_olympiads)C++20
0 / 100
1777 ms327680 KiB
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define ll long long
int n, k, c;
vector<vector<int>> scores;


ll convert(vector<int> bruh) {
    sort(bruh.begin(), bruh.end());
    return (ll)bruh[0] + bruh[1] * (ll)1000 + bruh[2] * (ll)1000000 + bruh[3] * (ll)1000000000 + bruh[4] * (ll)1000000000000 + bruh[5] * (ll)1000000000000000;
}


int totalscore(vector<int> bruh) {
    vector<int> valvec(k, 0);
    for (int i=0;i<k;i++) for (int j=0;j<k;j++) valvec[i] = max(valvec[i], scores[bruh[j]][i]);
    int valnum = 0;
    for (int i=0;i<k;i++) valnum += valvec[i];
    return valnum;
}


class compare {
    public: bool operator()(vector<int> a, vector<int> b) {
        return totalscore(a) < totalscore(b);
    }
};


int main() {
    cin >> n >> k >> c;
    scores = vector<vector<int>>(n, vector<int> (k));
    for (int i=0;i<n;i++) for (int j=0;j<k;j++) cin >> scores[i][j];


    vector<int> maxvec(k, 0);
    for (int i=0;i<n;i++) for (int j=0;j<k;j++) maxvec[j] = max(maxvec[j], scores[i][j]);
    vector<int> notchosen, chosen;
    vector<bool> ismax(k, false);
    for (int i=0;i<n;i++) {
        int flag = -1;
        for (int j=0;j<k;j++) if (!ismax[j] && (maxvec[j] == scores[i][j])) {flag = j; break;}
        if (flag == -1) {
            notchosen.pb(i);
        } else {
            for (int j=0;j<k;j++) if (maxvec[j] == scores[i][j]) ismax[j] = true;
            chosen.pb(i);
        }
    }
    while (chosen.size() != k) {
        chosen.pb(notchosen[notchosen.size() - 1]);
        notchosen.pop_back();
    }


    priority_queue<vector<int>, vector<vector<int>>, compare> pq; pq.push(chosen);
    unordered_set<ll> visited;
    vector<bool> curvals(n, false);
    while (true) {
        vector<int> bruh = pq.top(); pq.pop();
        for (int i: bruh) curvals[i] = true;
        vector<int> dumbruh = bruh;
        for (int i=0;i<k;i++) {
            for (int j=0;j<n;j++) {
                dumbruh[i] = j;
                if (!curvals[j] && visited.find(convert(dumbruh)) == visited.end()) pq.push(dumbruh);
                dumbruh[i] = bruh[i];
            }
        }
        visited.insert(convert(bruh));
        if (visited.size() == c) {
            cout << totalscore(bruh);
            break;
        }
        for (int i: bruh) curvals[i] = false;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...