oj.uz

답안 #128349

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
128349 2019-07-10T18:57:26 Z tutis Olympiads (BOI19_olympiads) C++17
13 / 100
 802 ms 35124 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 = 100000000;
bitset<dydis>M;
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);
	}
	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++)
		{
			int 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

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 15480 KB Output is correct
2 Correct 197 ms 18960 KB Output is correct
3 Correct 183 ms 18940 KB Output is correct
4 Correct 73 ms 6436 KB Output is correct

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 14584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 802 ms 35124 KB Output is correct
2 Correct 351 ms 6520 KB Output is correct
3 Incorrect 602 ms 25592 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 15480 KB Output is correct
2 Correct 197 ms 18960 KB Output is correct
3 Correct 183 ms 18940 KB Output is correct
4 Correct 73 ms 6436 KB Output is correct
5 Incorrect 49 ms 14584 KB Output isn't correct
6 Halted 0 ms 0 KB -