Submission #713722

#	Time	Username	Problem	Language	Result	Execution time	Memory
713722		tutis	Olympiads (BOI19_olympiads)	C++17	100 / 100	28 ms	756 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 N, K, C;
struct shard
{
	llist *forb = NULL;
	int k = 0;
	int score;
	int B[6];
	void eval()
	{
		vector<bool> gal(N, true);
		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 = 0; i < k; i++)
		{
			gal[B[i]] = false;
			for (int j = 0; j < K; j++)
				best[j] = max(best[j], A[B[i]][j]);
		}
		for (int j = k; j < K; j++)
		{
			int mx = -1;
			int id = -1;
			for (int i = 0; i < N; i++)
				if (gal[i])
					if (A[i][j] > mx)
					{
						mx = A[i][j];
						id = i;
					}
			if (id != -1)
			{
				gal[id] = false;
				B[j] = id;
				for (int k = j; k < K; k++)
					best[k] = max(best[k], A[id][k]);
			}
			else
			{
				score = -1;
				return;
			}
		}
		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[i][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