oj.uz

Submission #700903

# Submission time Handle Problem Language Result Execution time Memory
700903 2023-02-19T11:45:06 Z Jarif_Rahman Olympiads (BOI19_olympiads) C++17
100 / 100
 308 ms 41032 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;

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3028 KB Output is correct
2 Correct 9 ms 1108 KB Output is correct
3 Correct 8 ms 596 KB Output is correct
4 Correct 5 ms 492 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 9128 KB Output is correct
2 Correct 145 ms 6684 KB Output is correct
3 Correct 150 ms 18508 KB Output is correct
4 Correct 141 ms 12888 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 17852 KB Output is correct
2 Correct 52 ms 768 KB Output is correct
3 Correct 192 ms 14180 KB Output is correct
4 Correct 213 ms 14220 KB Output is correct
5 Correct 123 ms 5920 KB Output is correct
6 Correct 79 ms 1100 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3028 KB Output is correct
2 Correct 9 ms 1108 KB Output is correct
3 Correct 8 ms 596 KB Output is correct
4 Correct 5 ms 492 KB Output is correct
5 Correct 152 ms 9128 KB Output is correct
6 Correct 145 ms 6684 KB Output is correct
7 Correct 150 ms 18508 KB Output is correct
8 Correct 141 ms 12888 KB Output is correct
9 Correct 221 ms 17852 KB Output is correct
10 Correct 52 ms 768 KB Output is correct
11 Correct 192 ms 14180 KB Output is correct
12 Correct 213 ms 14220 KB Output is correct
13 Correct 123 ms 5920 KB Output is correct
14 Correct 79 ms 1100 KB Output is correct
15 Correct 308 ms 41032 KB Output is correct
16 Correct 255 ms 23760 KB Output is correct
17 Correct 193 ms 40368 KB Output is correct
18 Correct 198 ms 36640 KB Output is correct
19 Correct 49 ms 844 KB Output is correct