oj.uz

Submission #826619

# Submission time Handle Problem Language Result Execution time Memory
826619 2023-08-15T18:07:33 Z QwertyPi Olympiads (BOI19_olympiads) C++14
13 / 100
 2000 ms 63920 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

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

int n, k, c;

vector<int> C[6];
int t[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 mp_needed[10] = {0, 2000, 64, 24, 17, 14, 14};
int h(){
	int r = 0;
	for(int i = 0; i < k; i++) r = (r * mp_needed[k] + t[i]) % MOD;
	return r;
}

int s[8000000];
int sc_cnt[6000001];
void rec(int i){
	if(i == -1){
		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;
		}
		int sc = 0; for(int x = 0; x < k; x++) sc += C[x][t[x]];
		s[h()] = __C(n0, k); 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] == 0) fail = true;
				}
			}
			if(fail) continue;
			for(int j = 0; j < k; j++){
				if((1 << j) & m){
					t[j]--;
				}
			}
			tot += s[h()] * (pc % 2 ? -1 : 1);
			for(int j = 0; j < k; j++){
				if((1 << j) & m){
					t[j]++;
				}
			}
		}
		sc_cnt[sc] += tot;
		return;
	}
	for(int j = 0; j < C[i].size(); j++){
		t[i] = j;
		rec(i - 1);
		t[i] = 0;
	}
}

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++){
		vector<pair<int, int>> priority;
		for(int j = 0; j < n; j++) priority.push_back({a[j][i], j});
		sort(priority.begin(), priority.end(), [](auto p1, auto p2){ return p1.first > p2.first; });
		set<int> s;
		for(int j = 0; j < min(mp_needed[k], n); j++){
			s.insert(priority[j].first);
		}
		C[i] = vector<int>(s.begin(), s.end());
	}

	rec(k - 1);
	for(int sc = 6000000; sc >= 0; sc--){
		if(sc_cnt[sc] >= c){
			cout << sc << endl;
			return 0;
		}
		c -= sc_cnt[sc];
	}
}

Compilation message

olympiads.cpp: In function 'void rec(long long int)':
olympiads.cpp:72:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int j = 0; j < C[i].size(); j++){
      |                 ~~^~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2132 KB Output is correct
2 Correct 11 ms 468 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2085 ms 63920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Output is correct
2 Correct 9 ms 392 KB Output is correct
3 Incorrect 15 ms 568 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2132 KB Output is correct
2 Correct 11 ms 468 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Execution timed out 2085 ms 63920 KB Time limit exceeded
6 Halted 0 ms 0 KB -