#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(n < k) return 0;
int r = 1;
for(int i = 1; i <= k; i++){
r = r * (n - k + i) / i;
}
return r;
}
void rec(int i){
if(i == -1){
bool failed = false;
for(int x = 0; x < k; x++){
for(int y = 0; y < k; y++){
if(p[t[x]][x] > p[t[y]][x]){
failed = true; break;
}
}
if(failed) break;
}
if(failed) return;
vector<int> v;
for(int j = 0; j < k; j++) {
bool f = false;
for(int i = 0; i < v.size(); i++) if(v[i] == t[j]) { f = true; break; }
if(f) continue; v.push_back(t[j]);
}
int sum = 0; for(auto i : v) sum += r[i];
int n0 = 0, k0 = v.size();
for(int j = 0; j < n; j++){
if(find(v.begin(), v.end(), j) != v.end()) continue;
bool ok = true;
for(int x = 0; x < k; x++){
if(p[j][x] < p[t[x]][x]){
ok = false; break;
}
}
if(ok) n0++;
}
int sc = 0; for(int x = 0; x < k; x++) sc += a[t[x]][x];
if(__C(n0, k - k0) > 0) V.push_back({sc, __C(n0, k - k0)});
return;
}
for(int j = 0; j < C[i].size(); j++){
t[i] = C[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 < n; i++) r[i] = rng();
if(k == 1){
vector<int> b;
for(int i = 0; i < n; i++){
b.push_back(a[i][0]);
}
sort(b.begin(), b.end(), [](int x, int y){ return x > y; });
cout << b[c - 1] << endl;
return 0;
}else if(k == 2){
vector<int> b;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
b.push_back(max(a[i][0], a[j][0]) + max(a[i][1], a[j][1]));
}
}
sort(b.begin(), b.end(), [](int x, int y){ return x > y; });
cout << b[c - 1] << endl;
return 0;
}
set<int> s;
map<int, int> mp_needed;
mp_needed[3] = 40; // 24;
mp_needed[4] = 40; // 17;
mp_needed[5] = 40; // 14;
mp_needed[6] = 40; // 14;
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; });
for(int j = 0; j < n; j++){
p[priority[j].second][i] = j;
}
for(int j = 0; j < min(mp_needed[k], n); j++){
C[i].push_back(priority[j].second);
}
}
rec(k - 1);
sort(V.begin(), V.end(), [](auto a, auto b){ return a.first > b.first; });
for(auto [sc, cnt] : V){
if(cnt >= c){
cout << sc << endl;
return 0;
}
c -= cnt;
}
}
Compilation message
olympiads.cpp: In function 'void rec(long long int)':
olympiads.cpp:39:21: 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]
39 | for(int i = 0; i < v.size(); i++) if(v[i] == t[j]) { f = true; break; }
| ~~^~~~~~~~~~
olympiads.cpp:40:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
40 | if(f) continue; v.push_back(t[j]);
| ^~
olympiads.cpp:40:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
40 | if(f) continue; v.push_back(t[j]);
| ^
olympiads.cpp:58: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]
58 | for(int j = 0; j < C[i].size(); j++){
| ~~^~~~~~~~~~~~~
olympiads.cpp: In function 'int32_t main()':
olympiads.cpp:119:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
119 | for(auto [sc, cnt] : V){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1484 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1484 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1484 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2064 ms |
2392 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2054 ms |
8648 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1484 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1484 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1484 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1484 KB |
Output is correct |
| 5 |
Execution timed out |
2064 ms |
2392 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
