oj.uz

Submission #128362

# Submission time Handle Problem Language Result Execution time Memory
128362 2019-07-10T19:18:34 Z tutis Olympiads (BOI19_olympiads) C++17
100 / 100
 1018 ms 17912 KB 
/*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 sum = 0;
	for (int j = 0; j < k; j++)
	{
		int mx = 0;
		for (int i : x)
		{
			for (int j = 0; j < k; j++)
				mx = max(mx, a[i][j]);
		}
		sum += mx;
	}
	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))
				{
					while ((int)Q.size() > kth)
						Q.erase(Q.begin());
					if (M[abs(hh2 % dydis)] == false)
					{
						int gal = value(bb);
						bool ok = true;
						if ((int)Q.size() >= kth)
						{
							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;
				}
			}
		}
	}
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 11768 KB Output is correct
2 Correct 129 ms 14840 KB Output is correct
3 Correct 126 ms 13880 KB Output is correct
4 Correct 76 ms 7052 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 13816 KB Output is correct
2 Correct 55 ms 13432 KB Output is correct
3 Correct 56 ms 10232 KB Output is correct
4 Correct 53 ms 10104 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 725 ms 12260 KB Output is correct
2 Correct 665 ms 9304 KB Output is correct
3 Correct 735 ms 13164 KB Output is correct
4 Correct 712 ms 11512 KB Output is correct
5 Correct 748 ms 12792 KB Output is correct
6 Correct 27 ms 7164 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 11768 KB Output is correct
2 Correct 129 ms 14840 KB Output is correct
3 Correct 126 ms 13880 KB Output is correct
4 Correct 76 ms 7052 KB Output is correct
5 Correct 59 ms 13816 KB Output is correct
6 Correct 55 ms 13432 KB Output is correct
7 Correct 56 ms 10232 KB Output is correct
8 Correct 53 ms 10104 KB Output is correct
9 Correct 725 ms 12260 KB Output is correct
10 Correct 665 ms 9304 KB Output is correct
11 Correct 735 ms 13164 KB Output is correct
12 Correct 712 ms 11512 KB Output is correct
13 Correct 748 ms 12792 KB Output is correct
14 Correct 27 ms 7164 KB Output is correct
15 Correct 1018 ms 17912 KB Output is correct
16 Correct 814 ms 15608 KB Output is correct
17 Correct 630 ms 9592 KB Output is correct
18 Correct 892 ms 15608 KB Output is correct
19 Correct 637 ms 9436 KB Output is correct