Submission #1194181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194181		LucaIlie	Olympiads (BOI19_olympiads)	C++17	100 / 100	1905 ms	247996 KiB

olympiads

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

#if defined(__GNUC__)
#pragma GCC optimize("Ofast,unroll-loops,inline,fast-math")
#pragma GCC target("sse4.2,avx,avx2,bmi,bmi2,popcnt")
#pragma GCC optimize("no-stack-protector")
#endif

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

    int N, K;
    long long C;
    cin >> N >> K >> C;
    vector<vector<int>> score(N, vector<int>(K));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < K; j++)
            cin >> score[i][j];

    // precompute powers of N for encoding
    vector<ull> powN(K, 1);
    for (int i = 1; i < K; i++)
        powN[i] = powN[i - 1] * (ull)N;

    // 1) greedy “best” K‐set: one highest‐scoring unused contestant per event
    vector<bool> used(N, false);
    vector<int> startTeam;
    startTeam.reserve(K);
    for (int e = 0; e < K; e++) {
        int bestJ = 0, bestSc = -1;
        for (int j = 0; j < N; j++) {
            if (!used[j] && score[j][e] > bestSc) {
                bestSc = score[j][e];
                bestJ = j;
            }
        }
        used[bestJ] = true;
        startTeam.push_back(bestJ);
    }
    sort(startTeam.begin(), startTeam.end());

    auto encode = [&](const vector<int>& T) {
        ull s = 0;
        for (int i = 0; i < K; i++)
            s += (ull)T[i] * powN[i];
        return s;
    };
    auto fullScore = [&](const vector<int>& T) {
        int tot = 0;
        for (int e = 0; e < K; e++) {
            int m = 0;
            for (int x: T)
                m = max(m, score[x][e]);
            tot += m;
        }
        return tot;
    };

    struct Node {
        ull st;
        int sc;
    };
    struct Cmp {
        bool operator()(Node const& a, Node const& b) const {
            return a.sc < b.sc;
        }
    };

    priority_queue<Node, vector<Node>, Cmp> pq;
    unordered_set<ull> vis;
    vis.reserve((size_t)C * K + 10);

    ull s0 = encode(startTeam);
    pq.push({s0, fullScore(startTeam)});
    vis.insert(s0);

    vector<int> cur(K), newt(K);
    vector<int> base(K - 1), baseMax(K);
    bitset<500> in;

    // 2) best-first: pop best, expand all Hamming‐1 neighbors, repeat C–1 times
    for (long long iter = 1; iter < C; iter++) {
        auto [st, sc] = pq.top();
        pq.pop();

        // decode st → cur[]
        {
            ull x = st;
            for (int i = 0; i < K; i++) {
                cur[i] = int(x % (ull)N);
                x /= (ull)N;
            }
        }

        // for each position to remove
        for (int rem = 0; rem < K; rem++) {
            // build base[0..K-2]
            int t = 0;
            for (int i = 0; i < K; i++) {
                if (i == rem) continue;
                base[t++] = cur[i];
            }
            sort(base.begin(), base.end());

            // compute per-event max over those K-1 guys
            fill(baseMax.begin(), baseMax.end(), 0);
            for (int x: base)
                for (int e = 0; e < K; e++)
                    baseMax[e] = max(baseMax[e], score[x][e]);
            int baseScore = accumulate(baseMax.begin(), baseMax.end(), 0);

            // mark which are in the K-1 base
            in.reset();
            for (int x: base)
                in.set(x);

            // try every j not in that base
            for (int j = 0; j < N; j++) {
                if (in.test(j)) continue;

                // delta of adding j
                int delta = 0;
                for (int e = 0; e < K; e++) {
                    int sje = score[j][e];
                    if (sje > baseMax[e])
                        delta += sje - baseMax[e];
                }

                // build newt = sorted insertion of j into base[ ]
                bool done = false;
                int p = 0, q = 0;
                while (p < K) {
                    if (!done && (q == K - 1 || j < base[q])) {
                        newt[p++] = j;
                        done = true;
                    } else {
                        newt[p++] = base[q++];
                    }
                }

                // encode & push if unseen
                ull nst = 0;
                for (int i = 0; i < K; i++)
                    nst += (ull)newt[i] * powN[i];
                if (vis.insert(nst).second)
                    pq.push({nst, baseScore + delta});
            }
        }
    }

    // now the top of pq is the C-th best
    cout << pq.top().sc << "\n";
    return 0;
}

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