#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);
}
};
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;
int cur = 0;
map<vector<int>, bool> viz, vizz;
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;*/
bool mistaken = false;
for (int j = 0; j + 1 < k; j++)
if (idk[j] == idk[j + 1])
mistaken = true;
if (!mistaken)
{
if (!vizz[idk])
cur++;
vizz[idk] = true;
if (cur == c)
{
cout << value(idk);
return 0;
}
for (int j = 1; j <= k; j++)
{
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 j = 0; j < k; j++)
new_idk.push_back(ind[j + 1][new_nod.vv[j]]);
sort(new_idk.begin(), new_idk.end());*/
if (!viz[new_nod.vv])
pq.push(new_nod);
viz[new_nod.vv] = true;
}
}
}
else
{
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 (rau)
{
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 'int main()':
olympiads.cpp:86:9: warning: unused variable 'stt' [-Wunused-variable]
86 | int stt = 0;
| ^~~
olympiads.cpp:87:9: warning: unused variable 'vlm' [-Wunused-variable]
87 | int vlm = 1e9;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
1376 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1064 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1116 KB |
Output is correct |
| 4 |
Correct |
7 ms |
864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2025 ms |
96232 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
2136 KB |
Output is correct |
| 2 |
Correct |
22 ms |
1880 KB |
Output is correct |
| 3 |
Correct |
20 ms |
1884 KB |
Output is correct |
| 4 |
Correct |
23 ms |
2396 KB |
Output is correct |
| 5 |
Execution timed out |
2035 ms |
113800 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 |
8 ms |
1064 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1116 KB |
Output is correct |
| 4 |
Correct |
7 ms |
864 KB |
Output is correct |
| 5 |
Execution timed out |
2025 ms |
96232 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
