Submission #1187126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187126		kl0989e	Olympiads (BOI19_olympiads)	C++20	100 / 100	31 ms	1836 KiB

olympiads

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

vector<vi> peop;

struct searchable {
	int sum=0;
	vi inds;
	vector<bool> ban;
	int keep=0;

	searchable() {
		inds.resize(peop[0].size());
		ban.resize(peop.size(),0);
		keep=0;
	}

	void build(searchable* o, int num) {
		inds.resize(peop[0].size());
		ban=o->ban;
		keep=num;
		for (int i=0; i<keep; i++) {
			inds[i]=o->inds[i];
		}
		ban[o->inds[keep]]=1;
		build();
	}

	void build() {
		for (int i=keep; i<peop[0].size(); i++) {
			int ind=-1;
			int bst=-1;
			for (int j=0; j<peop.size(); j++) {
				if (ban[j]) {
					continue;
				}
				bool ok=1;
				for (int k=0; k<i; k++) {
					if (inds[k]==j) {
						ok=0;
						break;
					}
				}
				if (!ok) {
					continue;
				}
				if (peop[j][i]>bst) {
					ind=j;
					bst=peop[j][i];
				}
			}
			if (ind==-1) {
				sum=-1e9;
				return;
			}
			inds[i]=ind;
		}
		sum=0;
		for (int i=0; i<peop[0].size(); i++) {
			int bst=-1;
			for (int j=0; j<peop[0].size(); j++) {
				bst=max(bst,peop[inds[j]][i]);
			}
			sum+=bst;
		}
	}
};

class cmp {
	public:
	bool operator() (searchable* a, searchable* b) {
		return a->sum < b->sum;
	}
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	int n,k,c;
	cin >> n >> k >> c;
	peop.resize(n,vi(k));
	for (int i=0; i<n; i++) {
		for (int j=0; j<k; j++) {
			cin >> peop[i][j];
		}
	}
	searchable* a=new searchable();
	a->build();
	priority_queue<searchable*,vector<searchable*>,cmp> q;
	q.push(a);
	while (1) {
		searchable* a=q.top();
		q.pop();
		c--;
		if (c==0) {
			cout << a->sum << '\n';
			break;
		}
		for (int i=a->keep; i<k; i++) {
			searchable* t=new searchable();
			t->build(a,i);
			q.push(t);
		}
	}
	return 0;
}

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