oj.uz

Submission #683593

# Submission time Handle Problem Language Result Execution time Memory
683593 2023-01-18T19:53:06 Z four_specks Olympiads (BOI19_olympiads) C++17
100 / 100
 69 ms 1444 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Output is correct
2 Correct 8 ms 340 KB Output is correct
3 Correct 8 ms 324 KB Output is correct
4 Correct 6 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 596 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 8 ms 852 KB Output is correct
4 Correct 9 ms 572 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 340 KB Output is correct
2 Correct 14 ms 340 KB Output is correct
3 Correct 42 ms 924 KB Output is correct
4 Correct 46 ms 924 KB Output is correct
5 Correct 18 ms 456 KB Output is correct
6 Correct 4 ms 596 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Output is correct
2 Correct 8 ms 340 KB Output is correct
3 Correct 8 ms 324 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 6 ms 596 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 8 ms 852 KB Output is correct
8 Correct 9 ms 572 KB Output is correct
9 Correct 23 ms 340 KB Output is correct
10 Correct 14 ms 340 KB Output is correct
11 Correct 42 ms 924 KB Output is correct
12 Correct 46 ms 924 KB Output is correct
13 Correct 18 ms 456 KB Output is correct
14 Correct 4 ms 596 KB Output is correct
15 Correct 20 ms 492 KB Output is correct
16 Correct 36 ms 940 KB Output is correct
17 Correct 69 ms 1444 KB Output is correct
18 Correct 33 ms 680 KB Output is correct
19 Correct 13 ms 340 KB Output is correct