#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 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 sc_cnt[6000001];
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] + 2 == 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++){
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 < n; j++){
s.insert(priority[j].first);
}
s.insert(-1);
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] + 2 < 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:56: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]
56 | if(t[j] + 2 == C[j].size()) fail = true;
olympiads.cpp: In function 'int32_t main()':
olympiads.cpp:118:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
118 | auto [s, cnt, v] = pq.top(); pq.pop();
| ^
olympiads.cpp:125: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]
125 | if(v[i] + 2 < C[i].size()){
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
496 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
