oj.uz

Submission #700882

# Submission time Handle Problem Language Result Execution time Memory
700882 2023-02-19T10:15:03 Z Jarif_Rahman Olympiads (BOI19_olympiads) C++17
0 / 100
 38 ms 1876 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1172 KB Output is correct
2 Correct 13 ms 1876 KB Output is correct
3 Incorrect 21 ms 360 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -