Submission #128339

#	Time	Username	Problem	Language	Result	Execution time	Memory
128339		tutis	Olympiads (BOI19_olympiads)	C++17	13 / 100	2041 ms	56152 KiB

olympiads

/*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;
			}
		}
	}
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 31
• Subtask 3: 0 / 24
• Subtask 4: 0 / 32