Submission #1189976

#TimeUsernameProblemLanguageResultExecution timeMemory
1189976crafticatOlympiads (BOI19_olympiads)C++20
44 / 100
1425 ms327680 KiB
#include <bits/stdc++.h> using namespace std; #define F0R(i, n) for (int i = 0; i < n;i++) #define FOR(i, j, n) for(int i = j; i < n;i++) template<typename T> using V = vector<T>; using vi = V<int>; constexpr int INF = 1e9; V<vi> v; int n, k, c; int eval(vi a) { vi opt(k); for (auto i : a) { F0R(j, k) { opt[j] = max(opt[j], v[i][j]); } } return accumulate(opt.begin(), opt.end(), 0, [](int x, int y) { return x + y; }); } bool cmp(pair<int, vi> x, pair<int, vi> y) { return !(x < y); } V<vi> near(vi x) { V<vi> ans; F0R(i, k) { vi copy = x; F0R(j, n) { copy[i] = j; bool valid = 1; for (auto v : x) { if (v == j) valid = false; } if (valid) ans.push_back(copy); } } return ans; } int main() { cin >> n >> k >> c; v.resize(n, vi(k)); F0R(i, n) { F0R(j, k) cin >> v[i][j]; } vi opt(k); F0R(i, k) { F0R(j, n) { if (v[opt[i]][i] < v[j][i]) opt[i] = j; } } sort(opt.begin(), opt.end()); opt.erase( unique( opt.begin(), opt.end() ), opt.end() ); while (opt.size() < k) { F0R(i, n) { bool valid = true; for (auto x : opt) if (x == i) valid = false; if (valid) { opt.push_back(i); break; } } } map<vi, bool> vis; priority_queue<pair<int, vi>, V<pair<int, vi>>> pq; pq.push({eval(opt), opt}); int last = 0; while (!pq.empty() and c > 0) { auto [val, vec] = pq.top(); pq.pop(); sort(vec.begin(), vec.end()); if (vis[vec]) continue; last = val; vis[vec] = 1; c--; for (auto y : near(vec)) { sort(y.begin(), y.end()); if (vis[y]) continue; pq.push({eval(y),y}); } } cout << last << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...