/*
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |