#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int k = 4;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, _k, C; cin >> n >> _k >> C;
vector<vector<int>> v(n, vector<int>(k, 0));
for(int i = 0; i < n; i++) for(int j = 0; j < _k; j++) cin >> v[i][j];
vector<vector<int>> o(k, vector<int>(n)), pos(k, vector<int>(n));
for(int i = 0; i < k; i++){
for(int j = 0; j < n; j++) o[i][j] = j;
sort(o[i].begin(), o[i].end(), [&](int a, int b){
return v[a][i] > v[b][i];
});
for(int j = 0; j < n; j++) pos[i][o[i][j]] = j;
}
auto vec_to_ll = [&](vector<int> s){
sort(s.begin(), s.end());
ll x = 0, p = 1;
for(int i = 0; i < k; i++) x+=p*s[i], p*=n;
return x;
};
auto ll_to_vec = [&](ll x){
vector<int> s;
for(int i = 0; i < k; i++) s.pb(x%n), x/=n;
return s;
};
auto vec_sum = [&](vector<int> s){
int x = 0;
vector<int> mx(k, 0);
for(int i: s) for(int j = 0; j < k; j++) mx[j] = max(mx[j], v[i][j]);
for(int y: mx) x+=y;
return x;
};
set<pair<int, ll>> values;
{
vector<int> sth;
for(int i = 0; i < k; i++) for(int j = 0; j < n; j++){
if(find(sth.begin(), sth.end(), o[i][j]) != sth.end()) continue;
sth.pb({o[i][j]});
break;
}
values.insert({-vec_sum(sth), vec_to_ll(sth)});
}
int cnt = 0;
while(!values.empty()){
auto [X, curll] = *values.begin();
values.erase(values.begin());
X*=-1;
stack<ll> st;
set<ll> visited;
st.push(curll);
visited.insert(curll);
while(!st.empty()){
auto cur = ll_to_vec(st.top());
st.pop();
cnt++;
if(cnt == C){
cout << X << "\n";
exit(0);
}
for(int i = 0; i < k; i++) for(int j = 0; j < k; j++)
if(pos[i][cur[i]] != n-1 &&
find(cur.begin(), cur.end(), o[i][pos[i][cur[i]]+1]) == cur.end()) {
auto _cur = cur;
_cur[j] = o[i][pos[i][cur[i]]+1];
int diff = X-vec_sum(_cur);
ll x = vec_to_ll(_cur);
if(diff == 0){
if(visited.find(x) == visited.end()){
visited.insert(x);
st.push(x);
}
}
else{
auto it = lower_bound(values.begin(), values.end(), make_pair(-(X-diff), -1LL));
if(it == values.end() || it->f != -(X-diff)){
values.insert({-(X-diff), x});
}
}
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
