Submission #713730

#	Time	Username	Problem	Language	Result	Execution time	Memory
713730		tutis	Olympiads (BOI19_olympiads)	C++17	100 / 100	12 ms	852 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[500][6];
int P[6][500];
int N, K, C;
vector<bool> gal(512, true);
struct shard
{
	llist *forb = NULL;
	int k = 0;
	int score;
	int B[6];
	void eval()
	{
		for (llist *k = forb; k != NULL; k = k->nxt)
			gal[k->x] = false;
		int best[6];
		for (int i = 0; i < K; i++)
			best[i] = 0;
		for (int i = k; i < K; i++)
			B[i] = 0;
		for (int i = 0; i < k; i++)
		{
			gal[B[i]] = false;
			for (int j = 0; j < K; j++)
				best[j] = max(best[j], A[B[i]][j]);
		}
		bool ok = true;
		for (int j = k; j < K && ok; j++)
		{
			bool fnd = false;
			for (int t = 0; t < N && (!fnd); t++)
			{
				int i = P[j][t];
				if (gal[i])
				{
					gal[i] = false;
					B[j] = i;
					for (int k = j; k < K; k++)
						best[k] = max(best[k], A[i][k]);
					fnd = true;
				}
			}
			if (!fnd)
				ok = false;
		}
		if (ok) {
			score = 0;
			for (int j = 0; j < K; j++)
				score += best[j];
		}
		else
			score = -1;
		for (int i = 0; i < K; i++)
			gal[B[i]] = true;
		for (llist *k = forb; k != NULL; k = k->nxt)
			gal[k->x] = true;
	}
};
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[i][j];
	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[a][j] > A[b][j];});
	}
	priority_queue<shard>Q;
	{
		shard X;
		X.eval();
		Q.push(X);
	}
	for (int t = 1; t <= C - 1; t++)
	{
		shard s = Q.top();
		Q.pop();
		for (int f = s.k; f < K; f++)
		{
			shard t;
			t.forb = new llist(s.forb, s.B[f]);
			for (int j = 0; j < f; j++)
				t.B[j] = s.B[j];
			t.k = f;
			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: 13 / 13
• Subtask 2: 31 / 31
• Subtask 3: 24 / 24
• Subtask 4: 32 / 32