oj.uz

답안 #826633

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
826633 2023-08-15T18:36:37 Z QwertyPi Olympiads (BOI19_olympiads) C++14
0 / 100
 141 ms 872 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;

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(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]++;
				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:54: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]
   54 |     if(t[j] + 1 == C[j].size()) fail = true;
olympiads.cpp: In function 'int32_t main()':
olympiads.cpp:109:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |   auto [s, cnt, v] = pq.top(); pq.pop();
      |        ^
olympiads.cpp:116: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]
  116 |    if(v[i] + 1 < C[i].size()){

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 101 ms 872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 141 ms 388 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 488 KB Output isn't correct
2 Halted 0 ms 0 KB -