Submission #1157089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157089		vako_p	Olympiads (BOI19_olympiads)	C++20	100 / 100	6 ms	8260 KiB

olympiads

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define debug(x) cerr << '\n' << (#x) << " is " << (x) << " -> line: " << __LINE__ << endl;
//#define cerr if(false) cerr

const int mxN = 2e4;
ll n,k,c,a[mxN][10],x[mxN][10],idx[mxN],curr,val[mxN],mx,par[mxN];
bool ban[mxN][505],vis[mxN][505];
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>> q;
vector<pair<ll,ll>> v[10];
map<vector<ll>,bool> mp;

void f(ll at){
	ll cnt = 0;
	for(int j = 0; j < n; j++) cnt += 1 - ban[at][j];
	if(cnt <= k) return;
	for(int i = idx[at]; i < k; i++){
		curr++;
		par[curr] = at;
		idx[curr] = i;
		for(int j = 0; j < n; j++) ban[curr][j] = ban[at][j];
		for(int j = 0; j < i; j++){
			x[curr][j] = x[at][j];
			vis[curr][x[at][j]] = true;
		}
		ban[curr][x[at][i]] = true;
		for(int j = i; j < k; j++){
			for(auto it : v[j]){
				if(vis[curr][it.second] or ban[curr][it.second]) continue;
				vis[curr][it.second] = true;
				x[curr][j] = it.second;
				break;
			}
		}
		for(int j = 0; j < k; j++){
			mx = 0;
			for(int j1 = 0; j1 < k; j1++) mx = max(mx, a[x[curr][j1]][j]);
			val[curr] += mx;
		}
		q.push({val[curr], curr});
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k >> c;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < k; j++){
			cin >> a[i][j];
			v[j].pb({a[i][j], i});
		}
	}
	for(int j = 0; j < k; j++){
		sort(v[j].begin(), v[j].end());
		reverse(v[j].begin(), v[j].end());
		for(auto it : v[j]){
			if(vis[curr][it.second]) continue;
			vis[curr][it.second] = true;
			val[curr] += v[j][0].first;
			x[curr][j] = it.second;
			break;
		}
	}
	q.push({val[curr], curr});
	vector<ll> vv;
	while(!q.empty()){
		ll at = q.top().second; q.pop();
		c--;
		if(!c){
			cout << val[at] << '\n';
			break;
		}
		f(at);
	}
}
//12 4 100
//7 0 4 9
//3 0 8 4
//1 1 3 7
//5 1 3 4
//4 2 2 9
//7 0 4 9
//3 0 8 4
//1 1 3 7
//5 1 3 4
//4 2 2 9
//1 3 9 4
//1 9 0 9

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