| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 700925 | Jarif_Rahman | Olympiads (BOI19_olympiads) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
map<int, stack<ll>> st;
map<int, set<ll>> visited;
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<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;
}
int X = vec_sum(sth);
ll x = vec_to_ll(sth);
values.insert(-X);
st[X].push(x);
visited[X].insert(x);
}
int cnt = 0;
while(!values.empty()){
int X = *values.begin();
values.erase(values.begin());
X*=-1;
while(!st[X].empty()){
auto cur = ll_to_vec(st[X].top());
st[X].pop();
cnt++;
if(cnt == C){
cout << X << "\n";
exit(0);
}
vector<int> op;
for(int i = 0; i < k; i++){
int mx = -1;
for(x: cur) mx = max(mx, pos[i][x]);
if(mx+1 < n){
op.pb(o[i][mx+1]);
}
}
for(int i = 0; i < k; i++) for(int j: op){
auto _cur = cur;
_cur[i] = j;
int Y = vec_sum(_cur);
if(Y > X) continue;
ll x = vec_to_ll(_cur);
if(visited[Y].find(x) == visited[Y].end()){
visited[Y].insert(x);
st[Y].push(x);
}
if(Y < X) values.insert(-Y);
}
}
visited[X].clear();
}
}