oj.uz

Submission #128357

# Submission time Handle Problem Language Result Execution time Memory
128357 2019-07-10T19:03:58 Z tutis Olympiads (BOI19_olympiads) C++17
100 / 100
 1012 ms 18112 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 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, 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())
	{
		while ((int)Q.size() > kth)
			Q.erase(Q.begin());
		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))
				{
					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 152 ms 11896 KB Output is correct
2 Correct 159 ms 15096 KB Output is correct
3 Correct 147 ms 13828 KB Output is correct
4 Correct 90 ms 7160 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 13816 KB Output is correct
2 Correct 64 ms 13432 KB Output is correct
3 Correct 68 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 804 ms 12408 KB Output is correct
2 Correct 599 ms 9412 KB Output is correct
3 Correct 817 ms 13304 KB Output is correct
4 Correct 687 ms 11780 KB Output is correct
5 Correct 688 ms 12828 KB Output is correct
6 Correct 27 ms 7132 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 11896 KB Output is correct
2 Correct 159 ms 15096 KB Output is correct
3 Correct 147 ms 13828 KB Output is correct
4 Correct 90 ms 7160 KB Output is correct
5 Correct 76 ms 13816 KB Output is correct
6 Correct 64 ms 13432 KB Output is correct
7 Correct 68 ms 10232 KB Output is correct
8 Correct 53 ms 10104 KB Output is correct
9 Correct 804 ms 12408 KB Output is correct
10 Correct 599 ms 9412 KB Output is correct
11 Correct 817 ms 13304 KB Output is correct
12 Correct 687 ms 11780 KB Output is correct
13 Correct 688 ms 12828 KB Output is correct
14 Correct 27 ms 7132 KB Output is correct
15 Correct 1012 ms 18112 KB Output is correct
16 Correct 828 ms 15680 KB Output is correct
17 Correct 621 ms 9520 KB Output is correct
18 Correct 974 ms 15352 KB Output is correct
19 Correct 843 ms 9384 KB Output is correct