#include <bits/stdc++.h>
using namespace std;
int n,k,c;
int a[501][32];
vector<int> v[32];
struct team
{
int used[501];
int forb[501];
int p[32];
team()
{
for(int i=1;i<=n;i++)
used[i]=forb[i]=0;
}
bool operator<(const team&t)const
{
int sum=0;
for(int j=1; j<=k; j++)
{
int curr=v[j][t.p[j]];
sum+=a[curr][j];
}
int sum2=0;
for(int j=1; j<=k; j++)
{
int curr=v[j][p[j]];
sum2+=a[curr][j];
}
return sum2<sum;
}
};
priority_queue<team> q;
int h;
bool cmp(int i1,int i2)
{
return a[i1][h]>a[i2][h];
}
void read()
{
cin>>n>>k>>c;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=k; j++)
{
cin>>a[i][j];
v[j].push_back(i);
}
}
for(int i=1; i<=k; i++)
h=i,sort(v[i].begin(),v[i].end(),cmp);
for(int j=1; j<=k; j++)
v[j].push_back(0);
for(int i=1; i<=k; i++)
for(int j=n; j>=1; j--)
v[i][j]=v[i][j-1];
/*for(int i=1; i<=k; i++)
{
for(int j=1; j<=n; j++)
cout<<v[i][j]<<" ";
cout<<endl;
}*/
}
int comb[501][501];
void prec()
{
for(int i=0; i<=n; i++)
{
for(int j=0; j<=i; j++)
{
if(i==0||j==0)comb[i][j]=1;
else comb[i][j]=min(c,comb[i-1][j]+comb[i-1][j-1]);
//cout<<i<<" "<<j<<" "<<comb[i][j]<<endl;
}
}
}
int lvl[4000001];
map<set<int>,int> mp;
int num=0;
void solve()
{
team h;
num++;
for(int i=1; i<=k; i++)
h.p[i]=1,h.used[v[i][1]]=1;
q.push(h);
while(1)
{
team t=q.top();
q.pop();
int in=0,lf=0;
for(int i=1; i<=n; i++)
if(!t.used[i])
{
lf++;
}
set<int> s;
for(int i=1; i<=k; i++)
s.insert(v[i][t.p[i]]);
mp[s]++;
if(mp[s]>1)continue;
in=s.size();
c-=comb[lf][k-in];
int sum=0;
for(int d=1; d<=k; d++)
{
sum+=a[v[d][t.p[d]]][d];
//cout<<v[d][p[d][id]]<<" "<<d<<endl;
}
//cout<<sum<<endl;
if(c<=0)
{
cout<<sum<<endl;
return;
}
team nxt;
bool nun=1;
for(auto it=s.begin(); it!=s.end(); it++)
{
team curr=t;
num++;
int i=*it;
curr.forb[i]=1;
bool pos=1;
for(int d=1; d<=k; d++)
{
while(curr.p[d]<=n&&curr.forb[v[d][curr.p[d]]])curr.p[d]++;
if(curr.p[d]>n)pos=0;
else curr.used[v[d][curr.p[d]]]=1;
}
if(nun&&pos||pos&&nxt<curr)
{
nxt=curr;
num=0;
}
}
q.push(nxt);
}
}
void slow()
{
vector<int> ans;
if(k==2)
{
for(int i=1; i<=n; i++)
{
for(int j=i+1; j<=n; j++)
{
int sum=0;
for(int d=1; d<=k; d++)
sum+=max(a[i][d],a[j][d]);
ans.push_back(sum);
}
}
}
else
{
for(int i=1; i<=n; i++)
{
int sum=0;
for(int d=1; d<=k; d++)
sum+=a[i][d];
ans.push_back(sum);
}
}
sort(ans.begin(),ans.end());
cout<<ans[ans.size()-c]<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
read();
if(k<=2)slow();
else
{
prec();
solve();
}
return 0;
}
/*
9 2 7
1 4
8 3
10 3
3 2
7 5
6 9
3 7
2 4
9 3
*/
Compilation message
olympiads.cpp: In function 'void solve()':
olympiads.cpp:154:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
154 | if(nun&&pos||pos&&nxt<curr)
| ~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
988 KB |
Output is correct |
| 2 |
Correct |
6 ms |
988 KB |
Output is correct |
| 3 |
Correct |
5 ms |
988 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
988 KB |
Output is correct |
| 2 |
Correct |
6 ms |
988 KB |
Output is correct |
| 3 |
Correct |
5 ms |
988 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
