#include <bits/stdc++.h>
using namespace std;
int n, k, c;
int a[2005][10];
vector<int> ind[10];
struct cmp
{
bool operator ()(vector<int> A, vector<int> B) const{
int s1 = 0, s2 = 0;
for (int i = 0; i < k; i++)
s1 += a[ind[i + 1][A[i]]][i + 1], s2 += a[ind[i + 1][B[i]]][i + 1];
return s1 < s2;
}
};
int C(int x, int y)
{
if (y == 0)
return 1;
if (x < y)
return 0;
long long ww = 1;
for (int i = x; i > x - y; i--)
ww *= i;
for (int i = 1; i <= y; i++)
ww /= i;
if (ww >= (int)1e9)
ww = (int)1e9;
return ww;
}
int cnt(vector<int> nod)
{
for (int i = 0; i < k; i++)
{
for (int j = 0; j < k; j++)
{
if (i == j)
continue;
int cn1 = ind[i + 1][nod[i]], cn2 = ind[j + 1][nod[j]];
if (a[cn1][j + 1] > a[cn2][j + 1] or (a[cn1][j + 1] == a[cn2][j + 1] and cn1 < cn2))
return 0;
}
}
set<int> oameni;
for (int i = 0; i < k; i++)
oameni.insert(ind[i + 1][nod[i]]);
int lft = k - (int)oameni.size();
int cati = 0;
for (int i = 1; i <= n; i++)
{
bool ok = true;
for (int j = 1; j <= k; j++)
{
int cn = ind[j][nod[j - 1]];
if (a[i][j] > a[cn][j] or (a[i][j] == a[cn][j] and i <= cn))
ok = false;
}
if (ok)
cati++;
}
int ans = C(cati, lft);
return ans;
}
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)
{
if (a[A][i] != a[B][i])
{return a[A][i] > a[B][i];}
else{return A < B;}
});
}
/*for (int i = 1; i <= k; i++)
{
cout << i << " -> ";
for (auto it : ind[i])
cout << it << ' ';
cout << endl;
}*/
priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
int cate = 0;
vector<int> si;
for (int i = 1; i <= k; i++)
si.push_back(0);
pq.push(si);
int vlm = 1e9;
while (!pq.empty())
{
vector<int> nod = pq.top();
pq.pop();
int s = 0;
for (int i = 0; i < k; i++)
s += a[ind[i + 1][nod[i]]][i + 1];
if (s > vlm)
assert(false);
vlm = s;
cate += cnt(nod);
if (cate >= c)
{
cout << s;
return 0;
}
for (int i = 0; i < k; i++)
{
vector<int> nod2 = nod;
nod2[i]++;
if (nod2[i] < n)
pq.push(nod2);
}
}
return 0;
}
/*
5 2 10
1 7
2 5
3 10
4 8
2 9
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
352 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
1116 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
