Submission #646616

#	Time	Username	Problem	Language	Result	Execution time	Memory
646616		alextodoran	Olympiads (BOI19_olympiads)	C++17	100 / 100	619 ms	17016 KiB

olympiads

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 500;
const int K_MAX = 6;
const int C_MAX = 2000;

int N, K; ll C;
int score[N_MAX][K_MAX];

int ranking[K_MAX][N_MAX];
int position[K_MAX][N_MAX];

int getSum (vector <int> v) {
    int sum = 0;
    for (int j = 0; j < K; j++) {
        sum += score[ranking[j][v[j]]][j];
    }
    return sum;
}

ll countTeams (vector <int> v) {
    set <int> people;
    for (int j = 0; j < K; j++) {
        people.insert(ranking[j][v[j]]);
        for (int j1 = 0; j1 < K; j1++) {
            if (j1 != j && position[j][ranking[j1][v[j1]]] < v[j]) {
                return 0;
            }
        }
    }
    int in = (int) people.size();
    int out = K - in;
    int from = 0;
    for (int i = 0; i < N; i++) {
        bool ok = true;
        for (int j = 0; j < K; j++) {
            if (position[j][i] <= v[j]) {
                ok = false;
                break;
            }
        }
        if (ok == true) {
            from++;
        }
    }
    if (out > from) {
        return 0;
    }
    ll cnt = 1;
    for (int i = from - out + 1; i <= from; i++) {
        cnt *= i;
    }
    for (int i = 1; i <= out; i++) {
        cnt /= i;
    }
    return cnt;
}

bool used[N_MAX];
vector <int> sums;
void bk (int pos, int k) {
    if (k + (N - pos) < K) {
        return;
    }
    if (k == K) {
        int mx[K];
        fill(mx, mx + K, 0);
        for (int i = 0; i < N; i++) {
            if (used[i] == true) {
                for (int j = 0; j < K; j++) {
                    mx[j] = max(mx[j], score[i][j]);
                }
            }
        }
        int sum = 0;
        for (int j = 0; j < K; j++) {
            sum += mx[j];
        }
        sums.push_back(sum);
        return;
    }
    bk(pos + 1, k);
    used[pos] = true;
    bk(pos + 1, k + 1);
    used[pos] = false;
}

set <vector <int>> seen;

struct Option {
    int sum;
    vector <int> v;
};
bool operator < (const Option &x, const Option &y) {
    return x.sum < y.sum;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K >> C;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < K; j++) {
            cin >> score[i][j];
        }
    }
    if (N <= 40) {
        bk(0, 0);
        sort(sums.begin(), sums.end(), greater <int> ());
        cout << sums[C - 1] << "\n";
        return 0;
    }
    for (int j = 0; j < K; j++) {
        iota(ranking[j], ranking[j] + N, 0);
        sort(ranking[j], ranking[j] + N, [&] (const int &i1, const int &i2) {
            return score[i1][j] > score[i2][j];
        });
        for (int i = 0; i < N; i++) {
            position[j][ranking[j][i]] = i;
        }
    }
    priority_queue <Option> options;
    vector <int> init (K, 0);
    options.push(Option{getSum(init), init});
    while (options.empty() == false) {
        vector <int> v = options.top().v;
        options.pop();
        ll ct = countTeams(v);
        C -= ct;
        if (C <= 0) {
            cout << getSum(v) << "\n";
            break;
        }
        for (int j = 0; j < K; j++) {
            if (v[j] + 1 < N) {
                v[j]++;
                if (seen.find(v) == seen.end()) {
                    seen.insert(v);
                    options.push(Option{getSum(v), v});
                }
                v[j]--;
            }
        }
    }

    return 0;
}

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