Submission #445274

#	Time	Username	Problem	Language	Result	Execution time	Memory
445274		prvocislo	Olympiads (BOI19_olympiads)	C++17	100 / 100	68 ms	1668 KiB

olympiads

#include <bits/stdc++.h>
using namespace std;

struct node
{
    vector<bool> forbidden;
    vector<int> forced, team;
    int score;
};
inline bool operator<(const node &a, const node &b) { return a.score < b.score; }
int n, k, c, t[505][6];
void finish_team(node &no)
{
    no.team = no.forced;
    for (int i = no.team.size(); i < k; i++)
    {
        no.team.push_back(-1);
        for (int j = 0; j < n; j++) 
            if (!no.forbidden[j] && !count(no.team.begin(), no.team.end(), j) && (no.team.back() == -1 || t[j][i] > t[no.team.back()][i]))
                no.team.back() = j;
    }
    no.score = 0;
    for (int i = 0; i < k; i++)
    {
        int maxi = 0;
        for (int j : no.team) maxi = max(maxi, t[j][i]);
        no.score += maxi;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> c;
    for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) cin >> t[i][j];
    node st = {vector<bool>(n, false), {}, {}, 0};
    finish_team(st);
    priority_queue<node> pq;
    pq.push(st);
    for (int i = 0; i < c; i++)
    {
        node no = pq.top(); pq.pop();
        //cout << no.score << endl;
        if (i == c-1)
        {
            cout << no.score << "\n";
            return 0;
        }
        for (int i = no.forced.size(); i < k; i++)
        {
            node nw = no;
            nw.team.clear();
            nw.forbidden[no.team[i]] = true;
            finish_team(nw);
            if (!count(nw.team.begin(), nw.team.end(), -1))
                pq.push(nw);
            no.forced.push_back(no.team[i]);
        }
    }
    return 0;
}

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