oj.uz

Submission #646594

# Submission time Handle Problem Language Result Execution time Memory
646594 2022-09-30T09:13:39 Z alextodoran Olympiads (BOI19_olympiads) C++17
44 / 100
 2000 ms 246100 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;
}

set <vector <int>> seen;

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

    cin >> N >> K >> C;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < K; j++) {
            cin >> score[i][j];
        }
    }
    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 <pair <int, vector <int>>> options;
    options.push(make_pair(getSum(vector <int> (K, 0)), vector <int> (K, 0)));
    while (options.empty() == false) {
        int sum;
        vector <int> v;
        tie(sum, v) = options.top();
        options.pop();
        ll ct = countTeams(v);
        C -= ct;
        if (C <= 0) {
            cout << sum << "\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(make_pair(getSum(v), v));
                }
                v[j]--;
            }
        }
    }

    return 0;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2091 ms 246100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 24 ms 3008 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 4 ms 1236 KB Output is correct
7 Correct 5 ms 1236 KB Output is correct
8 Correct 5 ms 1236 KB Output is correct
9 Execution timed out 2091 ms 246100 KB Time limit exceeded
10 Halted 0 ms 0 KB -