Submission #1224198

#TimeUsernameProblemLanguageResultExecution timeMemory
122419812345678Olympiads (BOI19_olympiads)C++20
44 / 100
2095 ms17196 KiB
#include <bits/stdc++.h>

using namespace std;

const int nx=505;

int n, k, c, used[nx], dp[nx][nx];

struct students
{
    int s, idx, a[6];
    bool operator< (const students &o) const {return s<o.s;}
} s[nx];
students sub[6][nx];
vector<students> req;
priority_queue<int> pq;

void bruteforce(int idx, vector<int> cur, int cnt)
{
    //cout<<"dbg "<<idx<<'\n';
    if (idx==n)
    {
        if (cnt==k)
        {
            int sm=0;
            for (auto x:cur) sm+=x;
            pq.push(sm);
        }
        return;
    }
    if (cnt<k) 
    {
        vector<int> tmp(k);
        for (int i=0; i<k; i++) tmp[i]=max(cur[i], req[idx].a[i]);
        bruteforce(idx+1, tmp, cnt+1);
    }
    bruteforce(idx+1, cur, cnt);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k>>c;
    dp[0][0]=1;
    for (int i=1; i<=n+1; i++) for (int j=0; j<=i; j++) dp[i][j]=dp[i-1][j]+(j?dp[i-1][j-1]:0); //cout<<"dp "<<i<<' '<<j<<' '<<dp[i][j]<<'\n';
    for (int i=0; i<n; i++) for (int j=0; j<k; j++) cin>>s[i].a[j];
    for (int i=0; i<k; i++) for (int j=0; j<n; j++) sub[i][j]=s[j], sub[i][j].s=s[j].a[i], sub[i][j].idx=j;
    for (int i=0; i<k; i++) sort(sub[i], sub[i]+n), reverse(sub[i], sub[i]+n);
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<k; j++)
        {
            if (!used[sub[j][i].idx]&&req.size()<n)
            {
                used[sub[j][i].idx]=1;
                req.push_back(sub[j][i]);
            }
        }
    }
    //cout<<"debug "<<req.size()<<'\n';
    bruteforce(0, vector<int>(k), 0);
    while (--c) pq.pop();
    cout<<pq.top();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...