Submission #1178631

#TimeUsernameProblemLanguageResultExecution timeMemory
1178631DeMen100nsOlympiads (BOI19_olympiads)C++20
44 / 100
1624 ms327680 KiB
/* 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; State(vector <int> v, vector <vector<int>> &a, int k): v(v){ 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(chrono::steady_clock::now().time_since_epoch().count()); 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 <int> H(n); 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>>()); for(auto[val, id]: v){ if (!choose[id]){ choose[id] = true; opt.push_back(id); break; } } } sort(opt.begin(), opt.end()); priority_queue<State, vector<State>> pq; unordered_set <int> exist; pq.push(State(opt, a, k)); exist.insert(hash_state(opt)); while (c--){ State u = pq.top(); pq.pop(); if (c == 0){ cout << u.val << endl; return; } for(int i = 0; i < k; ++i){ for(int val = 0; val < n; ++val){ bool f = true; for(int i : u.v) f &= (i != val); if (!f) continue; vector <int> v = u.v; v[i] = val; int hsh = hash_state(v); if (exist.find(hsh) != exist.end()) continue; pq.push(State(v, a, k)); exist.insert(hsh); } } } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; for(int test = 1; test <= t; ++test){ 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...