Submission #128364

#	Time	Username	Problem	Language	Result	Execution time	Memory
128364		JustasZ	Olympiads (BOI19_olympiads)	C++14	100 / 100	114 ms	10772 KiB

olympiads

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
#define debug(...) cout << "[" << #__VA_ARGS__ << ": " << __VA_ARGS__ << "]\n"
#define rd() abs((int)rng())
using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn = 505;
const int mod = 1e9 + 7;
int n, k, c, arr[maxn][6];
struct shard
{
	int score;
	vector<int>choices, team;
	shard()
	{
		score = 0;
		choices = vector<int>(maxn, 0);
	}
	bool operator<(const shard &o) const
	{
		return score < o.score;
	}
};
shard null()
{
    shard a;
    a.score = -1;
    return a;
}
shard eval(shard a)
{
	vector<int>new_team;
	for(int i : a.team)
		if(a.choices[i] == 1)
			new_team.pb(i);
	for(int j = sz(new_team); j < k; j++)
	{
		int id = -1;
		for(int i = 0; i < n; i++)
		{
			if(!count(all(new_team), i) && a.choices[i] != -1)
			{
				if(id == -1 || arr[i][j] > arr[id][j])
					id = i;
			}
		}
		if(id == -1) return null();
		new_team.pb(id);
	}
	a.team = new_team;
	a.score = 0;
	for(int j = 0; j < k; j++)
	{
		int add = 0;
		for(int i : a.team)
			add = max(add, arr[i][j]);
		a.score += add;
	}
	return a;
}
int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0);
	cin >> n >> k >> c;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < k; j++)
			cin >> arr[i][j];
	shard st = eval(shard());
	priority_queue<shard>Q;
	Q.push(st);
	for(int i = 1; i <= c; i++)
	{
		shard a = Q.top();
		Q.pop();
		if(i == c)
		{
			cout << a.score << "\n";
			return 0;
		}
		for(int j = 0; j < k; j++)
		{
			if(a.choices[a.team[j]] == 0)
			{
				shard b = a;
				b.choices[b.team[j]] = -1;
				for(int jj = 0; jj < j; jj++)
					b.choices[b.team[jj]] = 1;
				b = eval(b);
				if(b.score != -1) Q.push(b);
			}
		}
	}
	return 0;
}

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