Submission #713738

#	Time	Username	Problem	Language	Result	Execution time	Memory
713738		tutis	Olympiads (BOI19_olympiads)	C++17	0 / 100	3 ms	608 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;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template<typename A, typename B>
using omap = tree <A, B, less<A>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename A>
using oset = tree <A, null_type, less<A>, rb_tree_tag, tree_order_statistics_node_update>;
struct llist
{
	int x;
	llist *nxt = NULL;
	llist(llist *nxt, int x): nxt(nxt), x(x)
	{

	}
};
int A[6][500];
int P[6][500];
int N, K, C;
struct shard
{
	llist *forb = NULL;
	int k = 0;
	int score;
	int B[6];
	void cr()
	{
		for (int j = 0; j < K; j++)
			for (int t = 0; t < N; t++)
			{
				bool ok = true;
				for (int k = 0; k < j; k++)
					if (P[k][B[k]] == P[j][t])
						ok = false;
				if (ok)
				{
					B[j] = t;
					break;
				}
			}
	}
	void eval()
	{
		int best[6];
		for (int i = 0; i < K; i++)
			best[i] = 0;
		for (int j = 0; j < K; j++)
		{
			for (int k = j; k < K; k++)
				best[k] = max(best[k], A[k][P[j][B[j]]]);
		}
		score = 0;
		for (int j = 0; j < K; j++)
			score += best[j];
	}
};
bool operator < (const shard &a, const shard &b)
{
	return a.score < b.score;
}
void solve()
{
	cin >> N >> K >> C;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < K; j++)
			cin >> A[j][i];
	for (int j = 0; j < K; j++)
	{
		for (int i = 0; i < N; i++)
			P[j][i] = i;
		sort(P[j], P[j] + N, [&](int a, int b) {return A[j][a] > A[j][b];});
	}
	priority_queue<shard>Q;
	{
		shard X;
		X.cr();
		X.eval();
		Q.push(X);
	}
	for (int t = 1; t <= C - 1; t++)
	{
		shard s = Q.top();
		Q.pop();

		vector<bool> gal(N, true);
		for (llist *k = s.forb; k != NULL; k = k->nxt)
			gal[k->x] = false;
		for (int j = 0; j < K; j++)
			gal[P[j][s.B[j]]] = false;

		for (int f = s.k; f < K; f++)
		{
			shard t;
			t.forb = new llist(s.forb, s.B[f]);
			for (int j = 0; j < K; j++)
				t.B[j] = s.B[j];
			t.k = f;
			bool ok = false;
			for (int k = s.B[f] + 1; k < N && (!ok); k++)
			{
				if (gal[P[f][k]])
				{
					ok = true;
					t.B[f] = k;
				}
			}
			if (ok) {
				t.eval();
				Q.push(t);
			}
		}
	}
	cout << Q.top().score << "\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
}

Compilation message (stderr)

olympiads.cpp: In constructor 'llist::llist(llist*, int)':
olympiads.cpp:26:9: warning: 'llist::nxt' will be initialized after [-Wreorder]
   26 |  llist *nxt = NULL;
      |         ^~~
olympiads.cpp:25:6: warning:   'int llist::x' [-Wreorder]
   25 |  int x;
      |      ^
olympiads.cpp:27:2: warning:   when initialized here [-Wreorder]
   27 |  llist(llist *nxt, int x): nxt(nxt), x(x)
      |  ^~~~~

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