제출 #1178742

#제출 시각아이디문제언어결과실행 시간메모리
1178742ollelOlympiads (BOI19_olympiads)C++20
44 / 100
1791 ms327680 KiB
#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;
vector<ll> scores;
set<vector<int>> visited;
priority_queue<pair<ll,vector<int>>> pq;

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

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

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

        tie(ans, 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);

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

    cout << ans << endl;
}



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...