Submission #826636

#	Time	Username	Problem	Language	Result	Execution time	Memory
826636		QwertyPi	Olympiads (BOI19_olympiads)	C++14	100 / 100	803 ms	15388 KiB

olympiads

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

int a[511][6];
int r[511];

int n, k, c;

vector<int> C[6];

vector<pair<int, int>> V;

int __C(int n, int k){
	if(k > n || k < 0) return 0;
	int r = 1;
	for(int i = 1; i <= k; i++){
		r = r * (n - k + i) / i;
	}
	return r;
}

const int A = 11354, MOD = 1e9 + 7;
int h(const vector<int>& t){
	int r = 0;
	for(int i = 0; i < k; i++) r = (r * A + t[i]) % MOD;
	return r;
}

map<int, int> s;
map<int, int> vis;

int calc_s(const vector<int>& t){
	int _h = h(t); if(s.count(_h)) return s[_h];
	int n0 = 0;
	for(int j = 0; j < n; j++){
		bool ok = true;
		for(int x = 0; x < k; x++){
			if(a[j][x] > C[x][t[x]]){
				ok = false; break;
			}
		}
		n0 += ok;
	}
	return s[_h] = __C(n0, k);
}

int calc(vector<int> t){
	int tot = 0;
	for(int m = 0; m < (1 << k); m++){
		bool fail = false;
		int pc = __builtin_popcount(m);
		for(int j = 0; j < k; j++){
			if((1 << j) & m){
				if(t[j] + 1 == C[j].size()) fail = true;
			}
		}
		if(fail) continue;
		for(int j = 0; j < k; j++){
			if((1 << j) & m){
				t[j]++;
			}
		}
		tot += calc_s(t) * (pc % 2 ? -1 : 1);
		for(int j = 0; j < k; j++){
			if((1 << j) & m){
				t[j]--;
			}
		}
	}
	return tot;
}

int sum(const vector<int>& t){
	int s = 0;
	for(int i = 0; i < k; i++){
		s += C[i][t[i]];
	}
	return s;
}

struct datum{
	int value, count; vector<int> v;
	bool operator< (const datum& o) const {
		return value < o.value;
	}
};

int32_t main(){
	random_device rd;
	mt19937 rng(rd());

	cin >> n >> k >> c;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < k; j++){
			cin >> a[i][j];
		}
	}

	for(int i = 0; i < k; i++){
		set<int> s; for(int j = 0; j < n; j++) s.insert(a[j][i]);
		C[i] = vector<int>(s.begin(), s.end());
		reverse(C[i].begin(), C[i].end());
	}

	priority_queue<datum> pq;
	vector<int> t(k);
	pq.push({sum(t), calc(t), t});
	while(!pq.empty()){
		auto [s, cnt, v] = pq.top(); pq.pop();
		if(!vis.count(h(v))) vis[h(v)] = true;
		else continue;
		if(cnt >= c){
			cout << s << endl;
			return 0;
		}
		c -= cnt;
		for(int i = 0; i < k; i++){
			if(v[i] + 1 < C[i].size()){
				v[i]++;
				if(!vis.count(h(v)))
					pq.push({sum(v), calc(v), v});
				v[i]--;
			}
		}
	}
}

Compilation message (stderr)

olympiads.cpp: In function 'long long int calc(std::vector<long long int>)':
olympiads.cpp:55:17: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     if(t[j] + 1 == C[j].size()) fail = true;
olympiads.cpp: In function 'int32_t main()':
olympiads.cpp:110:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  110 |   auto [s, cnt, v] = pq.top(); pq.pop();
      |        ^
olympiads.cpp:119:16: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |    if(v[i] + 1 < C[i].size()){

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