제출 #1178668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178668		DeMen100ns	Olympiads (BOI19_olympiads)	C++20	44 / 100	1663 ms	327680 KiB

olympiads

/*
Author : DeMen100ns (Vo Khac Trieu)
School: University of Science, VNU-HCM
Aim: 
- International Grandmaster Codeforces (2600) 
- ICPC World Final 2025
*/

#include <bits/stdc++.h>

#define int long long

using namespace std;

const long long INF = numeric_limits<long long>::max() / 2;
const int INF_int = 1e9 + 7;

struct State{
    int val;
    vector <int> v, ban;

    State(vector <int> v, vector<int> ban, vector <vector<int>> &a, int k): v(v), ban(ban){
        vector <int> ans(k, 0);
        for(int i = 0; i < k; ++i){
            for(int j = 0; j < k; ++j){
                ans[i] = max(ans[i], a[v[j]][i]);
            }
        }
        val = accumulate(ans.begin(), ans.end(), 0);
    }

    bool operator <(const State &a) const{
        return val < a.val;
    }
};

mt19937_64 rng(1234);

long long randint(long long l, long long r){
    return uniform_int_distribution <long long> (l, r) (rng);
}

double randdouble(double l, double r){
    return uniform_real_distribution <double> (l, r) (rng);
}

void solve(){
    int n, k, c; cin >> n >> k >> c;
    vector <vector<int>> a(n, vector<int>(k, 0));
    vector <vector<int>> order(n, vector<int>(k, 0));
    vector <int> H(n);
    vector <vector<array<int, 2>>> value(k);

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < k; ++j) cin >> a[i][j];
        H[i] = randint(5e17, 1e18);
    }

    auto hash_state = [&](vector <int> v){
        int hsh = 0;
        for(int i : v) hsh ^= H[i];
        return hsh;
    };
    
    vector <int> opt;
    vector <bool> choose(n, 0);
    for(int i = 0; i < k; ++i){
        vector <array<int, 2>> v;
        for(int j = 0; j < n; ++j){
            v.push_back({a[j][i], j});
        }
        sort(v.begin(), v.end(), greater<array<int, 2>>());
        value[i] = v;
        int ct = 0;
        bool g = false;
        for(auto[val, id]: v){
            order[id][i] = ++ct;
            if (!choose[id] && !g){
                g = true;
                choose[id] = true;
                opt.push_back(id);
            }
        }
    }
    sort(opt.begin(), opt.end());

    priority_queue<State, vector<State>> pq;
    unordered_set <int> exist;

    pq.push(State(opt, vector<int>(k, 0), a, k));
    exist.insert(hash_state(opt));

    while (c--){
        State u = pq.top(); pq.pop();

        // cout << u.val << " " << hash_state(u.v) << endl;
        // for(int i : u.v) cout << i << " "; cout << endl;

        if (c == 0){
            cout << u.val << endl;
            return;
        }

        for(int id = 0; id < k; ++id){
            for(int i = u.ban[id] + 1; i < n; ++i){
                bool valid = true;
                int new_i = value[id][i][1];
                for(int j = 0; j < k; ++j){
                    valid &= new_i != u.v[j];
                    //cerr << id << " " << i << " " << j << endl;
                    // valid &= order[new_i][j] > u.ban[j];
                }
                if (valid){
                    vector <int> new_v = u.v, new_ban = u.ban;
                    for(int sus = 0; sus < k; ++sus){
                        int tmp = new_v[sus];

                        new_v[sus] = new_i;
                        new_ban[id] = order[id][new_i];
                        int hsh = hash_state(new_v);

                        if (exist.find(hsh) == exist.end()){
                            pq.push(State(new_v, new_ban, a, k));
                            exist.insert(hsh);
                            break;
                        }

                        new_v[sus] = tmp;
                    }
                }
            }
        }

        assert(!pq.empty());

       // cerr << pq.size() << endl;
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int t = 1; // cin >> t;
    for(int test = 1; test <= t; ++test){
        solve();
    }
}

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