Submission #1194183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194183		LucaIlie	Olympiads (BOI19_olympiads)	C++17	100 / 100	970 ms	124960 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

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

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

    int N, K;
    long long C;
    cin >> N >> K >> C;

    static int score[500][6];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < K; j++)
            cin >> score[i][j];

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

    // greedy start‐team
    vector<int> start;
    start.reserve(K);
    vector<char> used(N, 0);
    for (int e = 0; e < K; e++) {
        int bj = 0, bs = -1;
        for (int j = 0; j < N; j++) {
            if (!used[j] && score[j][e] > bs) {
                bs = score[j][e];
                bj = j;
            }
        }
        used[bj] = 1;
        start.push_back(bj);
    }
    sort(start.begin(), start.end());

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

    // multiset keeps ascending‐by‐score; largest is *prev(end())
    multiset<Node, Asc> pq;
    unordered_set<ull> vis;
    vis.reserve((size_t)C * K + 10);

    // seed
    int tmp[6];
    for (int i = 0; i < K; i++) tmp[i] = start[i];
    pq.insert({encode(tmp), fullScore(tmp)});
    vis.insert(pq.begin()->st);

    static int cur[6], base[6], baseMax[6], newt[6];
    static bitset<500> in;

    // pop then expand C−1 times
    for (long long iter = 1; iter < C; iter++) {
        // 1) take the best
        auto itBest = prev(pq.end());
        Node top = *itBest;
        pq.erase(itBest);

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

        // 3) expand all Hamming‐1 neighbors
        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, base + (K - 1));

            // compute baseMax[e]
            for (int e = 0; e < K; e++) baseMax[e] = 0;
            for (int i = 0; i < K - 1; i++) {
                int x = base[i];
                for (int e = 0; e < K; e++)
                    baseMax[e] = max(baseMax[e], score[x][e]);
            }
            int bs = accumulate(baseMax, baseMax + K, 0);

            // mark used
            in.reset();
            for (int i = 0; i < K - 1; i++) in.set(base[i]);

            // try every j not in that base
            size_t limit = C - iter;
            for (int j = 0; j < N; j++) {
                if (in.test(j)) continue;
                int delta = 0;
                for (int e = 0; e < K; e++) {
                    int sje = score[j][e];
                    if (sje > baseMax[e]) delta += sje - baseMax[e];
                }
                // merge j into sorted
                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++];
                    }
                }
                ull nst = 0;
                for (int i = 0; i < K; i++) nst += powN[i] * (ull)newt[i];
                if (!vis.insert(nst).second) continue;

                Node nd{nst, bs + delta};
                // bounded‐insert into pq
                if (pq.size() < limit) {
                    pq.insert(nd);
                } else {
                    auto itMin = pq.begin();
                    if (nd.sc > itMin->sc) {
                        pq.erase(itMin);
                        pq.insert(nd);
                    }
                }
            }
        }
    }

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

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