Submission #1178739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178739		ollel	Olympiads (BOI19_olympiads)	C++20	44 / 100	1684 ms	327680 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 long long ll;
typedef vector<ll> vi;

ll n, c, k;
vector<vector<ll>> mat;

mt19937 rng(6215);
ll rand(ll maxr) {
    return uniform_int_distribution<ll>(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 eval = [&](vector<int> & inds) {
        vector<ll> res(k, 0);
        for (auto i : inds) rep(j,0,k) res[j] = max(res[j], mat[i][j]);
        ll 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);
    }

    sort(best.begin(), best.end());
    vector<ll> scores;
    set<vector<int>> visited;
    priority_queue<pair<ll,vector<int>>> pq;
    pq.push({eval(best), best});
    visited.insert(best);
    scores.push_back(eval(best));

    int iter = 1;
    while (iter < c && (!pq.empty())) {
        iter++;
        ll sc; vector<int> cur;
        tie(sc, cur) = pq.top(); pq.pop();
        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);
            sort(here.begin(), here.end());

            if (visited.find(here) != visited.end()) continue;

            visited.insert(here);
            ll score = eval(here);
            scores.push_back(score);

            pq.push({score, here});
        }
    }

    sort(scores.rbegin(), scores.rend());
    cout << scores[c-1] << endl;
}



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

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