Submission #1178704

#TimeUsernameProblemLanguageResultExecution timeMemory
1178704DeMen100nsOlympiads (BOI19_olympiads)C++20
100 / 100
46 ms1700 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, forced; vector <int> v; vector <bool> ban; State(vector <int> v, vector<bool> ban, int forced, vector <vector<int>> &a, int k) : v(v), ban(ban), forced(forced){ 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; } }; void solve(){ int n, k, c; cin >> n >> k >> c; vector <vector<int>> a(n, vector<int>(k, 0)); for(int i = 0; i < n; ++i){ for(int j = 0; j < k; ++j) cin >> a[i][j]; } vector <int> opt; vector <bool> choose(n, 0); for(int i = 0; i < k; ++i){ int ma = -1, ma_id = -1; for(int j = 0; j < n; ++j){ bool valid = true; for(int id : opt) valid &= j != id; if (valid && a[j][i] > ma){ ma = a[j][i]; ma_id = j; } } opt.push_back(ma_id); } priority_queue<State, vector<State>> pq; pq.push(State(opt, vector<bool>(n, 0), 0, a, k)); while (c--){ State u = pq.top(); pq.pop(); // cerr << "---" << endl << u.val << endl; // for(int i : u.v) cerr << i << " "; cerr << endl; if (c == 0){ cout << u.val << endl; return; } vector <bool> nban = u.ban; for(int id = u.forced; id < k; ++id){ nban[u.v[id]] = true; vector <int> opt; if (id > 0) opt = {u.v.begin(), u.v.begin() + id}; for(int event = id; event < k; ++event){ int ma = -1, ma_id = -1; for(int i = 0; i < n; ++i){ bool valid = !nban[i]; for(int j : opt) valid &= i != j; if (valid && a[i][event] > ma){ ma = a[i][event]; ma_id = i; } } if (ma_id != -1) opt.push_back(ma_id); else break; } // cerr << id << ": \n"; // for(int i : opt) cerr << i << " "; cerr << '\n'; if (opt.size() == k){ pq.push(State(opt, nban, id, a, k)); } } 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(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...