Submission #1178746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178746		ollel	Olympiads (BOI19_olympiads)	C++20	100 / 100	1973 ms	207420 KiB

olympiads

#pragma GCC optimize ("03")
#include <bitset>
#pragma GCC target ("avx2")

using namespace std;
#include <bits/stdc++.h>

#define rep(i,a,b) for (int i = a; i < b; i++)
#define pb push_back

typedef vector<int> vi;
typedef long long ll;

int n, c, k;
vector<vector<int>> mat;
set<ll> visited;
priority_queue<pair<int,ll>> pq;

mt19937 rng(6215);
int rand(int maxr) {
    return uniform_int_distribution<int>(0, maxr)(rng);
}

void solve() {
    cin >> n >> k >> c;
    mat.resize(n);

    rep(i,0,n) {
        mat[i].resize(k);
        rep(j,0,k) cin >> mat[i][j];
    }

    auto id2inds = [](ll id) {
        vector<int> inds;
        rep(j,0,k) {
            inds.push_back(id % n); id /= n;
        }
        return inds;
    };
    auto inds2id = [](vector<int> & inds) {
        sort(inds.begin(), inds.end());
        ll id = 0;
        rep(j,0,k) {
            id *= n;
            id += inds[j];
        }
        return id;
    };
    auto eval = [&](vector<int> & inds) {
        vector<int> res(k, 0);
        for (auto i : inds) rep(j,0,k) res[j] = max(res[j], mat[i][j]);
        int sum = 0;
        rep(j,0,k) sum += res[j];
    
        return sum;
    };

    vector<bool> in_best(n, false);
    vector<int> best;

    rep(j,0,k) {
        int I = -1;
        rep(i,0,n) {
            if (in_best[i]) continue;
            if (I == -1 || mat[i][j] > mat[I][j]) I = i;
        }
        in_best[I] = true;
        best.push_back(I);
    }

    pq.push({eval(best), inds2id(best)});
    visited.insert(inds2id(best));

    int iter = 1;
    int ans = 0;
    while (iter <= c && (!pq.empty())) {
        vector<int> cur; ll cid;

        tie(ans, cid) = pq.top(); pq.pop();
        iter++;
        
        cur = id2inds(cid);
        in_best.assign(n, false);
        for (auto i : cur) in_best[i] = true;
        rep(j,0,k) rep(i,0,n) {
            if (in_best[i]) continue;
            vector<int> here;
            rep(j2,0,k) if (j2 != j) here.push_back(cur[j2]);
            here.push_back(i);
            ll id = inds2id(here);
            if (visited.find(id) != visited.end()) continue;

            int score = eval(here);
            pq.push({score, id});
            visited.insert(id);
        }
    }

    cout << ans << endl;
}



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

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