oj.uz

Submission #826636

# Submission time Handle Problem Language Result Execution time Memory
826636 2023-08-15T18:40:32 Z QwertyPi Olympiads (BOI19_olympiads) C++14
100 / 100
 803 ms 15388 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 948 KB Output is correct
2 Correct 107 ms 3184 KB Output is correct
3 Correct 152 ms 5400 KB Output is correct
4 Correct 141 ms 4332 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 10 ms 448 KB Output is correct
4 Correct 10 ms 416 KB Output is correct
5 Correct 9 ms 436 KB Output is correct
6 Correct 9 ms 440 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 33 ms 948 KB Output is correct
6 Correct 107 ms 3184 KB Output is correct
7 Correct 152 ms 5400 KB Output is correct
8 Correct 141 ms 4332 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 10 ms 448 KB Output is correct
12 Correct 10 ms 416 KB Output is correct
13 Correct 9 ms 436 KB Output is correct
14 Correct 9 ms 440 KB Output is correct
15 Correct 244 ms 2696 KB Output is correct
16 Correct 146 ms 2456 KB Output is correct
17 Correct 803 ms 15388 KB Output is correct
18 Correct 476 ms 7900 KB Output is correct
19 Correct 1 ms 340 KB Output is correct