oj.uz

Submission #646616

# Submission time Handle Problem Language Result Execution time Memory
646616 2022-09-30T10:25:24 Z alextodoran Olympiads (BOI19_olympiads) C++17
100 / 100
 619 ms 17016 KB 
/**
 ____ ____ ____ ____ ____
||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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 17016 KB Output is correct
2 Correct 610 ms 16848 KB Output is correct
3 Correct 619 ms 16844 KB Output is correct
4 Correct 585 ms 16816 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 18 ms 1596 KB Output is correct
4 Correct 18 ms 2000 KB Output is correct
5 Correct 5 ms 1344 KB Output is correct
6 Correct 9 ms 968 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 614 ms 17016 KB Output is correct
6 Correct 610 ms 16848 KB Output is correct
7 Correct 619 ms 16844 KB Output is correct
8 Correct 585 ms 16816 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 18 ms 1596 KB Output is correct
12 Correct 18 ms 2000 KB Output is correct
13 Correct 5 ms 1344 KB Output is correct
14 Correct 9 ms 968 KB Output is correct
15 Correct 11 ms 1108 KB Output is correct
16 Correct 5 ms 852 KB Output is correct
17 Correct 15 ms 2012 KB Output is correct
18 Correct 13 ms 1744 KB Output is correct
19 Correct 1 ms 340 KB Output is correct