Submission #700903

#	Time	Username	Problem	Language	Result	Execution time	Memory
700903		Jarif_Rahman	Olympiads (BOI19_olympiads)	C++17	100 / 100	308 ms	41032 KiB

olympiads

#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){
            assert(i >= 0);
            assert(i < n);
            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++){
                vector<int> p;
                for(int x: cur) p.pb(pos[i][x]);
                sort(p.begin(), p.end());
                for(int j = 0; j < k; j++) if((j == k-1 && p[j]+1 < n) || (j != k-1 && p[j+1] > p[j]+1)){
                    op.pb(o[i][p[j]+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();
    }
}

• Subtask 1: 13 / 13
• Subtask 2: 31 / 31
• Subtask 3: 24 / 24
• Subtask 4: 32 / 32