#include <bits/stdc++.h>
using namespace std;
const int nx=505;
int n, k, c, used[nx], dp[nx][nx], tmp;
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;
multiset<int> ms;
void bruteforce(int idx, vector<int> cur, int cnt)
{
//cout<<"dbg "<<idx<<'\n';
if (idx==n)
{
if (cnt==k)
{
tmp++;
if (tmp>3e6) cout<<1/0;
int sm=0;
for (auto x:cur) sm+=x;
ms.insert(sm);
if (ms.size()>c) ms.erase(ms.begin());
}
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]&&dp[req.size()+1][k]<3000000)
{
used[sub[j][i].idx]=1;
req.push_back(sub[j][i]);
}
}
}
//cout<<"debug "<<req.size()<<'\n';
bruteforce(0, vector<int>(k), 0);
auto itr=prev(ms.end());
while (--c) --itr;
cout<<*itr;
}
Compilation message (stderr)
olympiads.cpp: In function 'void bruteforce(int, std::vector<int>, int)':
olympiads.cpp:26:33: warning: division by zero [-Wdiv-by-zero]
26 | if (tmp>3e6) cout<<1/0;
| ~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |