Submission #522792

#	Time	Username	Problem	Language	Result	Execution time	Memory
522792		LucaDantas	Olympiads (BOI19_olympiads)	C++17	0 / 100	2085 ms	89480 KiB

olympiads

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

constexpr int maxn = 510;

int n, k, C;

struct ct {
	int a[6];
	void read() { for(int i = 0; i < k; i++) scanf("%d", a+i); }
} AAA[maxn];

struct PQ {
	vector<int> ids;
	int val, index;

	PQ(vector<int> _ids={}, int _val=0, int _index=0) : ids(_ids), val(_val), index(_index) {}
	bool operator<(const PQ& o) const { return val < o.val; }
};

int get(vector<int> id, int lim) {
	int ans = 0;
	for(int i = 0; i <= lim; i++) {
		int aq = 0;
		for(int x : id)
			aq = max(aq, AAA[x].a[i]);
		ans += aq;
	}
	return ans;
}

int mx[6], best;

void db(vector<int> v) { putchar('{'); for(int x : v) printf(" %d", x); puts(" }"); }

map<vector<int>,bool> mark;

int main() {
	scanf("%d %d %d", &n, &k, &C);
	
	for(int i = 0; i < n; i++) {
		AAA[i].read();

		for(int j = 0; j < k; j++)
			mx[j] = max(mx[j], AAA[i].a[j]);
	}

	for(int j = 0; j < k; j++)
		best += mx[j];

	priority_queue<PQ> pq;
	pq.push(PQ({}, best, 0));

	int cnt = 0;
	while(1) {
		auto [ids, val, index] = pq.top(); pq.pop();

		if(index == k) {
			sort(ids.begin(), ids.end());
			if(mark[ids]) continue;
			mark[ids] = 1;
			
			++cnt;
			// db(ids);
			// printf("%d %d\n", cnt, val);
			
			if(cnt == C) {
				printf("%d\n", val);
				return 0;
			}
		}
		
		for(int i = 0; i < n; i++) {
			if(find(ids.begin(), ids.end(), i) == ids.end()) {
				ids.push_back(i);
				int v = get(ids, index), correction = 0;
				
				for(int j = index+1; j < k; j++)
					correction += mx[j];

				pq.push(PQ(ids, v+correction, index+1));
				ids.pop_back();
			}
		}
	}
}

Compilation message (stderr)

olympiads.cpp: In function 'int main()':
olympiads.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%d %d %d", &n, &k, &C);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp: In member function 'void ct::read()':
olympiads.cpp:11:48: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  void read() { for(int i = 0; i < k; i++) scanf("%d", a+i); }
      |                                           ~~~~~^~~~~~~~~~~

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