/*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)
{
ll w = 1;
for (int i = 0; i + 1 < k; i++)
{
ll x = (a / w) % 512;
ll ww = w * 512;
for (int j = i + 1; j < k; j++)
{
ll y = (a / ww) % 512;
if (x == y)
return true;
ww *= 512;
}
w *= 512;
}
return false;
}
int main()
{
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);
}
priority_queue<pair<int, ll>>Q;
ll xx = convert(best);
Q.push({value(xx), xx});
set<ll>M;
M.insert(get(xx));
multiset<ll>QQ;
QQ.insert(value(xx));
while (!Q.empty())
{
ll aa = Q.top().second;
int vall = Q.top().first;
Q.pop();
QQ.erase(--QQ.end());
if (blogai(aa))
continue;
if (kth == 1)
{
cout << vall << "\n";
return 0;
}
kth--;
for (int t = 0; t < n; t++)
{
int tt = t;
ll w = 511;
for (int i = 0; i < k; i++)
{
ll bb = ((aa & (~w)) | tt);
ll hh = get(bb);
if (M.find(hh) == M.end())
{
ll gal = value(bb);
bool ok = true;
if ((int)QQ.size() >= kth)
{
if (gal <= (*QQ.begin()))
ok = false;
}
if (ok)
{
M.insert(hh);
QQ.insert(gal);
Q.push({gal, bb});
}
}
w *= 512;
tt *= 512;
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
733 ms |
5352 KB |
Output is correct |
| 2 |
Correct |
883 ms |
11708 KB |
Output is correct |
| 3 |
Correct |
1025 ms |
11448 KB |
Output is correct |
| 4 |
Correct |
224 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
134 ms |
4664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2041 ms |
56152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
733 ms |
5352 KB |
Output is correct |
| 2 |
Correct |
883 ms |
11708 KB |
Output is correct |
| 3 |
Correct |
1025 ms |
11448 KB |
Output is correct |
| 4 |
Correct |
224 ms |
632 KB |
Output is correct |
| 5 |
Incorrect |
134 ms |
4664 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
