#include <bits/stdc++.h>
using namespace std;
long long n,k,c;
long long a[2048][2048];
vector<long long> v[2048];
long long p[2048][2048];
long long used[2048][2048];
long long forb[2048][2048];
struct team
{
long long id;
team() {}
team(long long i)
{
id=i;
}
bool operator<(const team&t)const
{
long long sum=0;
for(long long j=1; j<=k; j++)
{
long long curr=v[j][p[j][t.id]];
sum+=a[curr][j];
}
long long sum2=0;
for(long long j=1; j<=k; j++)
{
long long curr=v[j][p[j][id]];
sum2+=a[curr][j];
}
return sum2<sum;
}
};
priority_queue<team> q;
long long h;
bool cmp(long long i1,long long i2)
{
return a[i1][h]>a[i2][h];
}
void read()
{
cin>>n>>k>>c;
for(long long i=1; i<=n; i++)
{
for(long long j=1; j<=k; j++)
{
cin>>a[i][j];
v[j].push_back(i);
}
}
for(long long i=1; i<=k; i++)
h=i,sort(v[i].begin(),v[i].end(),cmp);
for(long long j=1; j<=k; j++)
v[j].push_back(0);
for(long long i=1; i<=k; i++)
for(long long j=n; j>=1; j--)
v[i][j]=v[i][j-1];
/*for(long long i=1; i<=k; i++)
{
for(long long j=1; j<=n; j++)
cout<<v[i][j]<<" ";
cout<<endl;
}*/
}
long long comb[2048][2048];
void prec()
{
for(long long i=0; i<=n; i++)
{
for(long long j=0; j<=i; j++)
{
if(i==0||j==0||i==j)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;
}
}
}
map<set<long long>,long long> mp;
long long num=0;
void solve()
{
num++;
for(long long i=1; i<=k; i++)
p[i][num]=1,used[v[i][1]][num]=1;
q.push(num);
while(1)
{
long long id=q.top().id;
q.pop();
long long in=0,lf=0;
for(long long i=1; i<=n; i++)
if(!used[i][id])
{
lf++;
}
set<long long> s;
for(long long i=1; i<=k; i++)
s.insert(v[i][p[i][id]]);
mp[s]++;
if(mp[s]>1)continue;
in=s.size();
c-=comb[lf][k-in];
long long sum=0;
for(long long d=1; d<=k; d++)
{
sum+=a[v[d][p[d][id]]][d];
//cout<<v[d][p[d][id]]<<" "<<d<<endl;
}
//cout<<sum<<endl;
if(c<=0)
{
cout<<sum<<endl;
return;
}
for(auto it=s.begin(); it!=s.end(); it++)
{
num++;
long long i=*it;
forb[i][num]=1;
for(long long j=1; j<=n; j++)
forb[j][num]=max(forb[j][num],forb[j][id]),
used[j][num]=used[j][id];
bool pos=1;
for(long long d=1; d<=k; d++)
{
while(p[d][num]<=n&&forb[v[d][p[d][num]]][num])p[d][num]++;
if(p[d][num]>n)pos=0;
else used[v[d][p[d][num]]][num]=1;
}
if(pos)q.push(num);
}
}
}
void slow()
{
vector<long long> ans;
if(k==3)
{
for(long long i=1; i<=n; i++)
{
for(long long j=i+1; j<=n; j++)
{
for(int l=j+1; l<=n; l++)
{
long long sum=0;
for(long long d=1; d<=k; d++)
sum+=max(a[i][d],max(a[l][d],a[j][d]));
ans.push_back(sum);
}
}
}
}
else if(k==2)
{
for(long long i=1; i<=n; i++)
{
for(long long j=i+1; j<=n; j++)
{
long long sum=0;
for(long long d=1; d<=k; d++)
sum+=max(a[i][d],a[j][d]);
ans.push_back(sum);
}
}
}
else
{
for(long long i=1; i<=n; i++)
{
long long sum=0;
for(long long 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();
slow();
prec();
solve();
return 0;
}
/*
9 4 120
1 4 3 4
8 3 1 2
10 3 8 5
3 2 3 10
7 5 5 8
6 9 2 1
3 7 6 5
2 4 9 8
9 3 1 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
21488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
21584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
21488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
