#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;
}
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;
return s1 < s2;
}
};
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;
pq.push(c0);
int stt = 0;
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());
//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)
{
cur++;
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_idk])
pq.push(new_nod);
viz[new_idk] = true;
}
}
}
else
{
viz[idk] = true;
for (int j = 1; j <= k; j++)
{
int cn = ind[j][nod.vv[j]];
bool rau = false;
for (int jj = 1; jj <= k; jj++)
{
if (jj != j)
{
int cnn = ind[jj][nod.vv[jj]];
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 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_idk])
pq.push(new_nod);
viz[new_idk] = true;
}
}
}
}
}
return 0;
}
Compilation message
olympiads.cpp: In function 'int main()':
olympiads.cpp:74:9: warning: unused variable 'stt' [-Wunused-variable]
74 | int stt = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
1620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
2140 KB |
Output is correct |
| 2 |
Correct |
48 ms |
3468 KB |
Output is correct |
| 3 |
Correct |
19 ms |
1884 KB |
Output is correct |
| 4 |
Correct |
21 ms |
2108 KB |
Output is correct |
| 5 |
Incorrect |
18 ms |
1372 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
