#include <bits/stdc++.h>
using namespace std;
int n, k, c;
int a[2005][10];
vector<int> ind[10];
struct conf
{
vector<int> vv;
};
int value(vector<int> idx)
{
int aa = 0;
for (int i = 1; i <= k; i++)
{
int mx = 0;
for (auto it : idx)
mx = max(mx, a[it][i]);
aa += mx;
}
return aa;
}
bool real(vector<int> ww)
{
sort(ww.begin(), ww.end());
for (int i = 0; i + 1 < k; i++)
if (ww[i] == ww[i + 1])
return false;
return true;
}
struct cmp
{
bool operator ()(conf A, conf B) const
{
vector<int> idkA, idkB;
for (int j = 0; j < k; j++)
idkA.push_back(ind[j + 1][A.vv[j]]);
for (int j = 0; j < k; j++)
idkB.push_back(ind[j + 1][B.vv[j]]);
int s1 = value(idkA);
int s2 = value(idkB);
//cout << "ufff " << s1 << ' ' << s2 << endl;
if (s1 != s2)
return s1 < s2;
return (int)real(idkA) < (int)real(idkB);
}
};
map<vector<int>, bool> viz, vizz;
int blabla;
int vls[10];
vector<int> sure;
int cur = 0;
void afis()
{
vector<int> uh = sure;
for (int i = 1; i <= blabla; i++)
uh.push_back(vls[i]);
sort(uh.begin(), uh.end());
for (int i = 1; i < uh.size(); i++)
if (uh[i] == uh[i - 1])
return;
if (!vizz[uh])
cur++;
vizz[uh] = true;
if (cur == c)
{
cout << value(uh);
exit(0);
}
}
void bkt(int pos)
{
if (pos == blabla + 1)
afis();
else
{
for (int i = 1; i <= n; i++)
{
bool nahh = false;
for (int j = 1; j < pos; j++)
if (vls[j] == i)
nahh = true;
for (auto it : sure)
if (it == i)
nahh = true;
if (nahh)
continue;
vls[pos] = i;
bkt(pos + 1);
}
}
}
int main()
{
cin >> n >> k >> c;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= k; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= k; j++)
ind[j].push_back(i);
for (int i = 1; i <= k; i++)
{
sort(ind[i].begin(), ind[i].end(), [i](int A, int B)
{
return a[A][i] > a[B][i];
});
}
/*for (int i = 1; i <= k; i++)
{
cout << "woow " << i << endl;
for (auto it : ind[i])
cout << it << ' ';
cout << endl << endl;
}*/
priority_queue<conf, vector<conf>, cmp> pq;
conf c0;
c0.vv.resize(k);
for (int i = 0; i < k; i++)
c0.vv[i] = 0;
viz[c0.vv] = true;
pq.push(c0);
int stt = 0;
int vlm = 1e9;
while (!pq.empty())
{
conf nod = pq.top();
pq.pop();
/*for (int j = 0; j < k; j++)
cout << nod.vv[j] << ' ';
cout << endl;*/
vector<int> idk;
for (int j = 0; j < k; j++)
idk.push_back(ind[j + 1][nod.vv[j]]);
sort(idk.begin(), idk.end());
//cout << value(idk) << endl;
//viz[idk] = true;
/*if (value(idk) > vlm)
assert(false);
vlm = value(idk);
for (auto it : idk)
cout << it << ' ';
cout << endl;
cout << endl;*/
vector<int> rp;
for (int i = 1; i < k; i++)
{
for (int j = 0; j < i; j++)
{
int cn = ind[j + 1][nod.vv[j]];
int cnn = ind[i + 1][nod.vv[i]];
if (cn == cnn)
rp.push_back(i);
}
}
set<int> neci;
for (auto it : idk)
neci.insert(it);
sure.clear();
for (auto it : neci)
sure.push_back(it);
int rm = k - neci.size();
blabla = rm;
bkt(1);
for (int j = 1; j <= k; j++)
{
//cout << "uuu" << endl;
/*int cn = ind[j][nod.vv[j - 1]];
bool rau = false;
for (int jj = 1; jj <= k; jj++)
{
if (jj != j)
{
int cnn = ind[jj][nod.vv[jj - 1]];
if (cnn == cn)
rau = true;
}
}*/
if (true)
{
conf new_nod;
new_nod.vv = nod.vv;
new_nod.vv[j - 1]++;
if (new_nod.vv[j - 1] < n)
{
/*vector<int> new_idk;
for (int jj = 0; jj < k; jj++)
new_idk.push_back(ind[jj + 1][new_nod.vv[jj]]);
sort(new_idk.begin(), new_idk.end());*/
if (!viz[new_nod.vv])
pq.push(new_nod);
viz[new_nod.vv] = true;
}
}
}
}
return 0;
}
/*
5 2 10
1 7
2 5
3 10
4 8
2 9
*/
Compilation message
olympiads.cpp: In function 'void afis()':
olympiads.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int i = 1; i < uh.size(); i++)
| ~~^~~~~~~~~~~
olympiads.cpp: In function 'int main()':
olympiads.cpp:132:9: warning: unused variable 'stt' [-Wunused-variable]
132 | int stt = 0;
| ^~~
olympiads.cpp:133:9: warning: unused variable 'vlm' [-Wunused-variable]
133 | int vlm = 1e9;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
1376 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1124 KB |
Output is correct |
| 3 |
Correct |
13 ms |
1340 KB |
Output is correct |
| 4 |
Correct |
6 ms |
864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2020 ms |
111584 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
2128 KB |
Output is correct |
| 2 |
Correct |
2 ms |
600 KB |
Output is correct |
| 3 |
Correct |
19 ms |
1980 KB |
Output is correct |
| 4 |
Correct |
26 ms |
2296 KB |
Output is correct |
| 5 |
Execution timed out |
2051 ms |
110444 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
1376 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1124 KB |
Output is correct |
| 3 |
Correct |
13 ms |
1340 KB |
Output is correct |
| 4 |
Correct |
6 ms |
864 KB |
Output is correct |
| 5 |
Execution timed out |
2020 ms |
111584 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
