제출 #445274

#제출 시각아이디문제언어결과실행 시간메모리
445274prvocisloOlympiads (BOI19_olympiads)C++17
100 / 100
68 ms1668 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...