/*input
5 4 4
7 0 4 9
3 0 8 4
1 1 3 7
5 1 3 4
4 2 2 9
*/
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
using namespace std;
typedef long long ll;
int a[500][6];
int n, k, kth;
int value(vector<int>&x)
{
int ret[6] = {0, 0, 0, 0, 0};
for (int i : x)
{
for (int j = 0; j < k; j++)
ret[j] = max(ret[j], a[i][j]);
}
int sum = 0;
for (int j = 0; j < k; j++)
sum += ret[j];
return sum;
}
int value(ll xx)
{
int ret[6] = {0, 0, 0, 0, 0};
for (int t = 0; t < k; t++)
{
int i = xx % 512;
xx /= 512;
for (int j = 0; j < k; j++)
ret[j] = max(ret[j], a[i][j]);
}
int sum = 0;
for (int j = 0; j < k; j++)
sum += ret[j];
return sum;
}
ll convert(vector<int>&x)
{
ll ret = 0;
for (int i : x)
ret = ret * 512 + i;
return ret;
}
vector<int>deconvert(ll x)
{
vector<int>ret;
for (int i = 0; i < k; i++)
{
ret.push_back(x % 512);
x /= 512;
}
return ret;
}
mt19937_64 gen(123123);
ll H[512];
ll get(ll x)
{
ll ret = 0;
for (int i = 0; i < k; i++)
{
ret ^= H[x % 512];
x /= 512;
}
return ret;
}
bool blogai(ll a, int x)
{
int plius = 0;
for (int i = 0; i < k; i++)
{
if ((a % 512) == x)
plius++;
a /= 512;
}
return plius == 1;
}
const int dydis = 150000000;
bitset<dydis>M;
int main()
{
srand(clock());
for (int i = 0; i < 512; i++)
{
H[i] = gen();
}
ios_base::sync_with_stdio(false), cin.tie(0);
cin >> n >> k >> kth;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < k; j++)
{
cin >> a[i][j];
}
}
vector<int>best;
{
for (int j = 0; j < k; j++)
{
pair<int, int>mx = { -1, -1};
for (int i = 0; i < n; i++)
{
mx = max(mx, {a[i][j], i});
}
if (find(best.begin(), best.end(), mx.second) == best.end())
best.push_back(mx.second);
}
}
while ((int)best.size() < k)
{
int x = rand() % n;
if (find(best.begin(), best.end(), x) == best.end())
best.push_back(x);
}
set<pair<int, ll>>Q;
ll xx = convert(best);
Q.insert({value(xx), xx});
M[abs(get(xx) % dydis)] = true;
while (!Q.empty())
{
auto it = --Q.end();
ll aa = it->second;
int vall = it->first;
Q.erase(it);
if (kth == 1)
{
cout << vall << "\n";
return 0;
}
kth--;
ll hh = get(aa);
int mini = Q.begin()->first;
for (int t = 0; t < n; t++)
{
ll tt = t;
ll w = 511;
ll hh1 = hh ^ H[t];
ll aaa = aa;
for (int i = 0; i < k; i++)
{
ll bb = ((aa & (~w)) | tt);
ll hh2 = hh1 ^ H[aaa % 512];
if (blogai(bb, t))
{
if (M[abs(hh2 % dydis)] == false)
{
int gal = value(bb);
bool ok = true;
if ((int)Q.size() >= 2000)
{
if (gal <= mini)
ok = false;
}
if (ok)
{
M[abs(hh2 % dydis)] = true;
Q.insert({gal, bb});
mini = min(mini, gal);
}
}
w *= 512;
tt *= 512;
aaa /= 512;
}
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
200 ms |
21624 KB |
Output is correct |
| 2 |
Correct |
178 ms |
25008 KB |
Output is correct |
| 3 |
Correct |
239 ms |
24952 KB |
Output is correct |
| 4 |
Correct |
86 ms |
11128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
23716 KB |
Output is correct |
| 2 |
Correct |
79 ms |
22052 KB |
Output is correct |
| 3 |
Correct |
65 ms |
15472 KB |
Output is correct |
| 4 |
Correct |
68 ms |
18936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2023 ms |
131244 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
200 ms |
21624 KB |
Output is correct |
| 2 |
Correct |
178 ms |
25008 KB |
Output is correct |
| 3 |
Correct |
239 ms |
24952 KB |
Output is correct |
| 4 |
Correct |
86 ms |
11128 KB |
Output is correct |
| 5 |
Correct |
116 ms |
23716 KB |
Output is correct |
| 6 |
Correct |
79 ms |
22052 KB |
Output is correct |
| 7 |
Correct |
65 ms |
15472 KB |
Output is correct |
| 8 |
Correct |
68 ms |
18936 KB |
Output is correct |
| 9 |
Execution timed out |
2023 ms |
131244 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
