/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 500;
const int K_MAX = 6;
const int C_MAX = 2000;
int N, K; ll C;
int score[N_MAX][K_MAX];
int ranking[K_MAX][N_MAX];
int position[K_MAX][N_MAX];
int getSum (vector <int> v) {
int sum = 0;
for (int j = 0; j < K; j++) {
sum += score[ranking[j][v[j]]][j];
}
return sum;
}
ll countTeams (vector <int> v) {
set <int> people;
for (int j = 0; j < K; j++) {
people.insert(ranking[j][v[j]]);
for (int j1 = 0; j1 < K; j1++) {
if (j1 != j && position[j][ranking[j1][v[j1]]] < v[j]) {
return 0;
}
}
}
int in = (int) people.size();
int out = K - in;
int from = 0;
for (int i = 0; i < N; i++) {
bool ok = true;
for (int j = 0; j < K; j++) {
if (position[j][i] <= v[j]) {
ok = false;
break;
}
}
if (ok == true) {
from++;
}
}
if (out > from) {
return 0;
}
ll cnt = 1;
for (int i = from - out + 1; i <= from; i++) {
cnt *= i;
}
for (int i = 1; i <= out; i++) {
cnt /= i;
}
return cnt;
}
set <vector <int>> seen;
bool used[N_MAX];
vector <int> sums;
void bk (int pos, int k) {
if (k + (N - pos + 1) < K) {
return;
}
if (k == K) {
int mx[K];
fill(mx, mx + K, 0);
for (int i = 0; i < N; i++) {
if (used[i] == true) {
for (int j = 0; j < K; j++) {
mx[j] = max(mx[j], score[i][j]);
}
}
}
int sum = 0;
for (int j = 0; j < K; j++) {
sum += mx[j];
}
sums.push_back(sum);
return;
}
bk(pos + 1, k);
used[pos] = true;
bk(pos + 1, k + 1);
used[pos] = false;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> K >> C;
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++) {
cin >> score[i][j];
}
}
if (N <= 40) {
bk(1, 0);
sort(sums.begin(), sums.end());
cout << sums[C - 1] << "\n";
return 0;
}
for (int j = 0; j < K; j++) {
iota(ranking[j], ranking[j] + N, 0);
sort(ranking[j], ranking[j] + N, [&] (const int &i1, const int &i2) {
return score[i1][j] > score[i2][j];
});
for (int i = 0; i < N; i++) {
position[j][ranking[j][i]] = i;
}
}
priority_queue <pair <int, vector <int>>> options;
options.push(make_pair(getSum(vector <int> (K, 0)), vector <int> (K, 0)));
while (options.empty() == false) {
int sum;
vector <int> v;
tie(sum, v) = options.top();
options.pop();
ll ct = countTeams(v);
C -= ct;
if (C <= 0) {
cout << sum << "\n";
break;
}
for (int j = 0; j < K; j++) {
if (v[j] + 1 < N) {
v[j]++;
if (seen.find(v) == seen.end()) {
seen.insert(v);
options.push(make_pair(getSum(v), v));
}
v[j]--;
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
6 ms |
468 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| 4 |
Correct |
21 ms |
2964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
620 ms |
16776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2084 ms |
240192 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
6 ms |
468 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| 4 |
Correct |
21 ms |
2964 KB |
Output is correct |
| 5 |
Incorrect |
620 ms |
16776 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
