Submission #361336

#	Time	Username	Problem	Language	Result	Execution time	Memory
361336		tutis	Olympiads (BOI19_olympiads)	C++17	100 / 100	152 ms	26784 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
*/
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename X>
using ordered_map = tree<T, X, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename X>
using fast_map = cc_hash_table<T, X>;
//using ull = __uint128_t;
using ull = unsigned long long;
using ll = long long;
using ld = long double;
mt19937_64 rng(123);
const ll mod = 1000000007;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, k, c;
	cin >> n >> k >> c;
	vector<vector<int>> A(n, vector<int>(k));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < k; j++)
			cin >> A[i][j];
	vector<vector<int>> p(k, vector<int>(n));
	vector<vector<int>> q(k, vector<int>(n));
	for (int i = 0; i < k; i++)
	{
		iota(p[i].begin(), p[i].end(), 0);
		sort(p[i].begin(), p[i].end(), [&](int x, int y) {return A[x][i] > A[y][i];});
		for (int j = 0; j < n; j++)
			q[i][p[i][j]] = j;
	}
	priority_queue<pair<int, vector<int>>>Q;
	{
		int sum = 0;
		set<int>a;
		for (int i = 0; i < k; i++)
		{
			sum += A[p[i][0]][i];
			a.insert(p[i][0]);
		}
		while (a.size() < k)
			a.insert(rng() % k);
		Q.push({sum, vector<int>(a.begin(), a.end())});
	}
	set<ull>BUV;
	vector<ull>H(n);
	for (int i = 0; i < n; i++)
		H[i] = rng();
	auto f = [&](const vector<int>&v)->ull
	{
		ll r = 0;
		for (int i = 0; i < k; i++)
			r ^= H[v[i]];
		return r;
	};
	auto eval = [&](const vector<int>&v)->int
	{
		int ret = 0;
		for (int i = 0; i < k; i++)
		{
			int mx = 0;
			for (int j = 0; j < k; j++)
				mx = max(mx, A[v[j]][i]);
			ret += mx;
		}
		return ret;
	};
	while (!Q.empty())
	{
		int sum = Q.top().first;
		vector<int>v = Q.top().second;
		Q.pop();
		ull h = f(v);
		if (BUV.count(h))
			continue;
		BUV.insert(h);
		c--;
		if (c == 0)
		{
			cout << sum << "\n";
			return 0;
		}
		for (int i = 0; i < k; i++)
		{
			for (int j = 0; j < k; j++)
			{
				for (int a = 0; a < k; a++)
				{
					int c = q[a][v[j]];
					if (c != n - 1)
					{
						int buvo = v[i];
						v[i] = p[a][c + 1];
						bool ok = true;
						for (int c = 0; c < k; c++)
							for (int d = 0; d < c; d++)
								if (v[d] == v[c])
									ok = false;
						if (ok)
							Q.push({eval(v), v});
						v[i] = buvo;
					}
				}
			}
		}
	}
}

Compilation message (stderr)

olympiads.cpp: In function 'int main()':
olympiads.cpp:56:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |   while (a.size() < k)
      |          ~~~~~~~~~^~~

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