Submission #700882

#	Time	Username	Problem	Language	Result	Execution time	Memory
700882		Jarif_Rahman	Olympiads (BOI19_olympiads)	C++17	0 / 100	38 ms	1876 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;

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});
                    }
                }
            }
        }
    }
}

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