Submission #1178745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178745		ollel	Olympiads (BOI19_olympiads)	C++20	44 / 100	970 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 vector<int> vi;

int n, c, k;
vector<vector<int>> mat;
set<vector<int>> visited;
priority_queue<pair<int,vector<int>>> 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 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);
    }

    sort(best.begin(), best.end());

    pq.push({eval(best), best});

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

        tie(ans, cur) = pq.top(); pq.pop();

        if (visited.find(cur) != visited.end()) continue;
        
        visited.insert(cur);
        iter++;
        
        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());

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

    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: 0 / 24
• Subtask 4: 0 / 32