Submission #361300

#	Time	Username	Problem	Language	Result	Execution time	Memory
361300		tutis	Olympiads (BOI19_olympiads)	C++17	0 / 100	2067 ms	28840 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));
	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];});
	}
	priority_queue<pair<int, vector<int>>>Q;
	{
		int sum = 0;
		vector<int>c(k, 0);
		for (int i = 0; i < k; i++)
			sum += A[p[i][0]][i];
		Q.push({sum, c});
	}
	set<vector<int>>buv;
	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[p[i][v[i]]];
		return r;
	};
	while (!Q.empty())
	{
		int sum = Q.top().first;
		vector<int>v = Q.top().second;
		Q.pop();
		ll h = f(v);
		if (BUV.count(h))
			continue;
		BUV.insert(h);
		bool ok = true;
		for (int i = 0; i < k; i++)
			for (int j = 0; j < i; j++)
				ok &= p[i][v[i]] != p[j][v[j]];
		if (ok)
		{
			c--;
			if (c == 0)
			{
				cout << sum << "\n";
				return 0;
			}
		}
		for (int i = 0; i < k; i++)
		{
			if (v[i] != n - 1)
			{
				v[i]++;
				int sum_ = 0;
				for (int j = 0; j < k; j++)
				{
					int mx = 0;
					for (int c = 0; c < k; c++)
						mx = max(mx, A[p[c][v[c]]][j]);
					sum_ += mx;
				}
				Q.push({sum_, v});
				v[i]--;
			}
		}
	}
}

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