Submission #826618

#TimeUsernameProblemLanguageResultExecution timeMemory
826618QwertyPiOlympiads (BOI19_olympiads)C++14
13 / 100
2067 ms63924 KiB
#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 + k) % 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 (stderr)

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++){
      |                 ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...