Submission #1326942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326942		DeathIsAwe	Olympiads (BOI19_olympiads)	C++20	44 / 100	2102 ms	209428 KiB

olympiads

#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 pownum(int a, int b) {
    ll bruh = 1;
    for (int i=0;i<b;i++) bruh *= (ll)a;
    return bruh;
}


ll convert(vector<int> bruh) {
    sort(bruh.begin(), bruh.end());
    ll sus = 0;
    for (int i=0;i<k;i++) sus += bruh[i] * pownum(1000, i);
    return sus;
}


vector<int> revconvert(ll bruh) {
    vector<int> asdf;
    for (int i=0;i<k;i++) {
        asdf.pb(bruh % 1000);
        bruh /= 1000;
    }
    return asdf;
}


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;
}


int32_t 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();
    }


    chosen.pb(0);
    chosen[k] = totalscore(chosen);
    pair<int,ll> chosenpair = mp(totalscore(chosen), convert(chosen));
    priority_queue<pair<int,ll>> pq; pq.push(chosenpair);
    unordered_set<ll> tobevis; tobevis.insert(chosenpair.ss);
    int count = 0;
    vector<bool> curvals(n, false);
    pair<int,ll> toppair, temp;
    vector<int> bruh, dumbruh, curmax;
    int curtotalscore, tempcurtotal;
    while (true) {
        toppair = pq.top(); pq.pop();
        bruh = revconvert(toppair.ss);
        for (int i=0;i<k;i++) curvals[bruh[i]] = true;
        dumbruh = bruh;
        for (int i=0;i<k;i++) {
            curmax = vector<int>(6, 0);
            for (int j=0;j<k;j++) {
                for (int l=0;l<k;l++) {
                    if (l == i) continue;
                    curmax[j] = max(curmax[j], scores[bruh[l]][j]);
                }
            }
            curtotalscore = 0;
            for (int j=0;j<k;j++) curtotalscore += curmax[j];
            for (int j=0;j<n;j++) {
                dumbruh[i] = j;
                if (!curvals[j] && tobevis.find(convert(dumbruh)) == tobevis.end()) {
                    tempcurtotal = curtotalscore;
                    for (int l=0;l<k;l++) tempcurtotal += max(0, scores[dumbruh[i]][l] - curmax[l]);
                    temp = mp(tempcurtotal, convert(dumbruh));
                    pq.push(temp);
                    tobevis.insert(temp.ss);
                }
                dumbruh[i] = bruh[i];
            }
        }
        count += 1;
        if (count == c) {
            cout << toppair.ff;
            break;
        }
        for (int i=0;i<k;i++) curvals[bruh[i]] = false;
    }
}

• Subtask 1: 13 / 13
• Subtask 2: 31 / 31
• Subtask 3: 0 / 24
• Subtask 4: 0 / 32