제출 #1194160

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194160		LucaIlie	Olympiads (BOI19_olympiads)	C++17	44 / 100	2100 ms	219616 KiB

olympiads

#include <bits/stdc++.h>

using namespace std;

struct team {
    long long state;
    int score;

    bool operator<(const team &x) const {
        return score < x.score;
    }
};

const int MAX_N = 500;
const int MAX_K = 6;
int n, k;
int score[MAX_N][MAX_K];
bool inBestTeam[MAX_N];
long long put[MAX_N];
priority_queue<team> pq;
unordered_map<long long, bool> vis;

vector<int> getTeamMembers(team t) {
    vector<int> members;
    for (int i = 0; i < k; i++)
        members.push_back(t.state / put[i] % n);
    return members;
}

team encodeTeam(vector<int> members) {
    sort(members.begin(), members.end());
    team t = {0, 0};
    for (int i = 0; i < k; i++) {
        int maxx = 0;
        for (int j = 0; j < k; j++)
            maxx = max(maxx, score[members[j]][i]);
        t.score += maxx;
        t.state += put[i] * members[i];
    }
    return t;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int c;
    cin >> n >> k >> c;
    c--;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++)
            cin >> score[i][j];
    }

    vector<int> bestTeam;
    for (int i = 0; i < k; i++) {
        put[i] = (i == 0 ? 1 : put[i - 1] * n);
        int maxx = 0, pos = 0;
        for (int j = 0; j < n; j++) {
            if (score[j][i] > maxx && !inBestTeam[j]) {
                maxx = score[j][i];
                pos = j;
            }
        }
        inBestTeam[pos] = true;
        bestTeam.push_back(pos);
    }

    team start = encodeTeam(bestTeam);
    pq.push(start);
    vis[start.state] = true;
    while (!pq.empty() && c > 0) {
        auto x = pq.top();
        pq.pop();

        c--;

        vector<int> crtTeam = getTeamMembers(x);
        /* printf("%lld %d\n", x.state, x.score); */
        /* for (int x: crtTeam) */
        /*     printf("%d ", x); */
        /* printf("\n"); */
        for (int i = 0; i < k; i++) {
            vector<int> newTeam = crtTeam;
            swap(newTeam[i], newTeam[newTeam.size() - 1]);
            newTeam.pop_back();
            for (int j = 0; j < n; j++) {
                bool inTeam = false;
                for (int l = 0; l < k - 1; l++) {
                    if (newTeam[l] == j)
                        inTeam = true;
                }
                if (inTeam)
                    continue;

                newTeam.push_back(j);
                team y = encodeTeam(newTeam);
                if (!vis[y.state]) {
                    vis[y.state] = true;
                    pq.push(y);
                }
                newTeam.pop_back();
            }
        }
    }

    cout << pq.top().score << "\n";

    return 0;
}

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