Submission #683593

#	Time	Username	Problem	Language	Result	Execution time	Memory
683593		four_specks	Olympiads (BOI19_olympiads)	C++17	100 / 100	69 ms	1444 KiB

olympiads

#include <bits/stdc++.h>

using namespace std;

namespace
{
    template <typename T>
    bool ckmin(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }

    template <typename T>
    bool ckmax(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }

} // namespace

void solve()
{
    int n, k, c;
    cin >> n >> k >> c, --c;

    vector a(n, vector<long>(k));
    for (int i = 0; i < n; i++)
    {
        for (int l = 0; l < k; l++)
            cin >> a[i][l];
    }

    auto eval = [&](const vector<bool> &ban) -> pair<long, vector<int>>
    {
        vector<int> take(k);

        vector<bool> done(n, 0);
        for (int l = 0; l < k; l++)
        {
            long x = -1;
            int j = -1;
            for (int i = 0; i < n; i++)
            {
                if (!ban[i] && !done[i])
                {
                    if (ckmax(x, a[i][l]))
                        j = i;
                }
            }
            take[l] = j;
            done[j] = 1;
        }

        long score = 0;
        for (int l = 0; l < k; l++)
        {
            long x = 0;
            for (int m = 0; m < k; m++)
                ckmax(x, a[take[m]][l]);
            score += x;
        }

        return pair(score, take);
    };

    priority_queue<tuple<long, int, vector<int>, vector<bool>, int>> pq;
    {
        vector<bool> ban(n, 0);
        auto [score, take] = eval(ban);
        pq.emplace(score, 0, take, ban, 0);
    }
    for (int i = 0, id = 1; i < c; i++)
    {
        auto [p_score, p_x, p_take, p_ban, p_nxt] = pq.top();
        pq.pop();

        int can = 0;
        for (int j = 0; j < n; j++)
        {
            if (!p_ban[j])
                can++;
        }

        if (can - 1 < k)
            continue;

        vector ban = p_ban;
        for (int nxt = p_nxt; nxt < k; nxt++)
        {
            ban[p_take[nxt]] = 1;
            auto [score, take] = eval(ban);
            pq.emplace(score, id++, take, ban, nxt);
            ban[p_take[nxt]] = 0;
        }
    }

    long res = get<0>(pq.top());

    cout << res << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

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