oj.uz

답안 #128339

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
128339 2019-07-10T18:24:13 Z tutis Olympiads (BOI19_olympiads) C++17
13 / 100
 2000 ms 56152 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)
{
	ll w = 1;
	for (int i = 0; i + 1 < k; i++)
	{
		ll x = (a / w) % 512;
		ll ww = w * 512;
		for (int j = i + 1; j < k; j++)
		{
			ll y = (a / ww) % 512;
			if (x == y)
				return true;
			ww *= 512;
		}
		w *= 512;
	}
	return false;
}
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);
	}
	priority_queue<pair<int, ll>>Q;
	ll xx = convert(best);
	Q.push({value(xx), xx});
	set<ll>M;
	M.insert(get(xx));
	multiset<ll>QQ;
	QQ.insert(value(xx));
	while (!Q.empty())
	{
		ll aa = Q.top().second;
		int vall = Q.top().first;
		Q.pop();
		QQ.erase(--QQ.end());
		if (blogai(aa))
			continue;
		if (kth == 1)
		{
			cout << vall << "\n";
			return 0;
		}
		kth--;
		for (int t = 0; t < n; t++)
		{
			int tt = t;
			ll w = 511;
			for (int i = 0; i < k; i++)
			{
				ll bb = ((aa & (~w)) | tt);
				ll hh = get(bb);
				if (M.find(hh) == M.end())
				{
					ll gal = value(bb);
					bool ok = true;
					if ((int)QQ.size() >= kth)
					{
						if (gal <= (*QQ.begin()))
							ok = false;
					}
					if (ok)
					{
						M.insert(hh);
						QQ.insert(gal);
						Q.push({gal, bb});
					}
				}
				w *= 512;
				tt *= 512;
			}
		}
	}
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 733 ms 5352 KB Output is correct
2 Correct 883 ms 11708 KB Output is correct
3 Correct 1025 ms 11448 KB Output is correct
4 Correct 224 ms 632 KB Output is correct

Subtask #2
0 / 31.0

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

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2041 ms 56152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 733 ms 5352 KB Output is correct
2 Correct 883 ms 11708 KB Output is correct
3 Correct 1025 ms 11448 KB Output is correct
4 Correct 224 ms 632 KB Output is correct
5 Incorrect 134 ms 4664 KB Output isn't correct
6 Halted 0 ms 0 KB -