Submission #1194180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194180		LucaIlie	Olympiads (BOI19_olympiads)	C++17	0 / 100	94 ms	8772 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
#ifdef _MSC_VER
#pragma optimize("gt", on)
#pragma inline_depth(255)
#pragma inline_recursion(on)
#pragma comment(linker, "/STACK:20000000")
#endif

constexpr int MAX_N = 500;
constexpr int MAX_K = 6;

int n, k, c;
int score[MAX_N][MAX_K];
ull putPow[MAX_K];

bitset<MAX_N> usedInTeam;
int curMax[MAX_K];

struct Team {
    ull state;
    int score;
    bool operator<(const Team &o) const { return score < o.score; }
    bool operator>(const Team &o) const { return score > o.score; }
};

static inline Team makeTeam(const int members[], bool calcScore) {
    // ensure non-decreasing
    for (int i = k - 1; i > 0; --i)
        if (members[i] < members[i - 1])
            swap(const_cast<int &>(members[i]), const_cast<int &>(members[i - 1]));

    Team t{0, 0};
    for (int i = 0; i < k; ++i) {
        if (calcScore) {
            int m = 0;
            for (int j = 0; j < k; ++j)
                m = max(m, score[members[j]][i]);
            t.score += m;
        }
        t.state += putPow[i] * members[i];
    }
    return t;
}

static inline void unpackTeam(ull st, int members[]) {
    for (int i = 0; i < k; ++i) {
        members[i] = (st / putPow[i]) % n;
    }
}

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

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

    // precompute bases
    putPow[0] = 1;
    for (int i = 1; i < k; ++i)
        putPow[i] = putPow[i - 1] * n;

    // greedy start team
    int best[MAX_K];
    for (int i = 0; i < k; ++i) {
        int pos = 0, mx = -1;
        for (int j = 0; j < n; ++j) {
            if (!usedInTeam.test(j) && score[j][i] > mx) {
                mx = score[j][i];
                pos = j;
            }
        }
        usedInTeam.set(pos);
        best[i] = pos;
    }
    sort(best, best + k);

    unordered_set<ull> vis;
    vis.reserve(1 << 20);
    vis.max_load_factor(0.5f);

    priority_queue<Team> pq;
    Team start = makeTeam(best, true);
    pq.push(start);
    vis.insert(start.state);

    int members[MAX_K], newArr[MAX_K];
    while (!pq.empty() && c-- > 0) {
        Team cur = pq.top();
        pq.pop();
        unpackTeam(cur.state, members);

        // prepare base (k-1) usedInTeam and curMax
        usedInTeam.reset();
        fill(curMax, curMax + k, 0);
        for (int i = 0, idx = 0; i < k; ++i) {
            newArr[idx++] = members[i];
            if (idx == k - 1) break;
        }
        for (int i = 0; i < k - 1; ++i) {
            int m = newArr[i];
            usedInTeam.set(m);
            for (int j = 0; j < k; ++j)
                curMax[j] = max(curMax[j], score[m][j]);
        }

        int baseScore = accumulate(curMax, curMax + k, 0);

        // small min-heap for top-c neighbors
        struct Keeper {
            vector<Team> v;
            int cap;
            Keeper(int C) : cap(C) { v.reserve(C); }
            void push(const Team &t) {
                if ((int)v.size() < cap) {
                    v.push_back(t);
                    if ((int)v.size() == cap) make_heap(v.begin(), v.end(), greater<>());
                } else if (t.score > v.front().score) {
                    pop_heap(v.begin(), v.end(), greater<>());
                    v.back() = t;
                    push_heap(v.begin(), v.end(), greater<>());
                }
            }
        } keeper(c + 2);

        for (int i = 0; i < k; ++i) {
            // build the k-1 base excluding members[i]
            int idx = 0;
            for (int j = 0; j < k; ++j)
                if (j != i)
                    newArr[idx++] = members[j];
            sort(newArr, newArr + (k - 1));

            // try replacing with each j not in base
            for (int j = 0; j < n; ++j) {
                if (usedInTeam.test(j)) continue;
                int delta = 0;
                for (int l = 0; l < k; ++l)
                    if (score[j][l] > curMax[l])
                        delta += score[j][l] - curMax[l];
                newArr[k - 1] = j;
                Team nb = makeTeam(newArr, false);
                nb.score = baseScore + delta;
                if (vis.insert(nb.state).second)
                    keeper.push(nb);
            }
        }

        for (auto &t: keeper.v)
            pq.push(t);
    }

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

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