제출 #1194169

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

olympiads

#include <bits/stdc++.h>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

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];
int maxx[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, bool calcScore) {
    sort(members.begin(), members.end());
    team t = {0, 0};
    for (int i = 0; i < k; i++) {
        int maxx = 0;
        if (calcScore) {
            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, true);
    pq.push(start);
    vis[start.state] = true;
    while (!pq.empty() && c > 0) {
        auto x = pq.top();
        pq.pop();

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

                int newScore = crtScore;
                for (int l = 0; l < k; l++) {
                    if (score[j][l] > maxx[l])
                        newScore += score[j][l] - maxx[l];
                }
                newTeam.push_back(j);
                team y = encodeTeam(newTeam, false);
                y.score = newScore;
                if (!vis[y.state]) {
                    vis[y.state] = true;
                    newTeams.push_back(y);
                }
                newTeam.pop_back();
            }
        }
        sort(newTeams.begin(), newTeams.end());
        reverse(newTeams.begin(), newTeams.end());
        for (int i = 0; i < c && i < (int)newTeams.size(); i++)
            pq.push(newTeams[i]);
        c--;
    }

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

    return 0;
}

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