#include <bits/stdc++.h>
// #define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 500;
int n, k, c;
int scores[MAXN][6];
int sort_pos[MAXN][6]; // what position in the array are you
pii sorted[6][MAXN];
ll choose[MAXN][6];
unordered_set<ll> vis;
class team {
public:
int members[6]; // indices of members in array
int num_below = 0;
int score = 0;
int num_distinct = 0;
team() {
fill(members, members+k, 0);
num_below = n;
for (int i = 0; i < k; i++) score += sorted[i][0].first;
for (int i = 0; i < k; i++) {
bool u = 1;
for (int j = 0; j < i; j++) {
if (sorted[i][0].second == sorted[j][0].second) {
u = 0;
break;
}
}
num_distinct += u;
}
}
void cpy(team &t) {
for (int i = 0; i < k; i++) members[i] = t.members[i];
num_below = t.num_below;
score = t.score;
num_distinct = t.num_distinct;
}
void get_same(int p, vector<int> &v) {
for (int i = 0; i < k; i++)
if (sorted[i][members[i]].second == sorted[p][members[p]].second)
v.push_back(i);
}
bool valid(int v) {
for (int i = 0; i < k; i++) {
if (sort_pos[v][i] < members[i]) return 0;
}
return 1;
}
bool dist(int v) {
for (int i = 0; i < k; i++) {
if (i == v) continue;
if (sorted[i][members[i]].second == sorted[v][members[v]].second) return 0;
}
return 1;
}
team(team &prv, int p) { // incrementing pos p
cpy(prv);
vector<int> s_vals;
get_same(p, s_vals);
num_distinct--;
num_below--;
for (int v: s_vals) {
score -= sorted[v][members[v]].first;
do {
if (members[v] == n-1) {
score = -1;
return;
}
members[v]++;
} while (!valid(sorted[v][members[v]].second));
score += sorted[v][members[v]].first;
num_distinct += dist(v);
}
}
ll amt() {
return choose[num_below-num_distinct][k-num_distinct];
}
ll get_hsh() {
ll hsh = 0;
for (int i = 0; i < k; i++) {
hsh *= n;
hsh += members[i];
}
return hsh;
}
};
bool operator<(const team &a, const team &b) {
return (a.score == b.score) ? (&a < &b) : (a.score < b.score);
}
priority_queue<team> pq;
void make_dupe(team &t) {
for (int i = 0; i < k; i++) {
pq.push(team(t, i));
}
}
void make_options(int pos, int left, int best[], vector<int> &ops, int s = 0) {
if (pos == n) {
if (left) return;
ops.push_back(s);
return;
}
make_options(pos+1, left, best, ops, s);
if (left == 0) return;
int nbest[6];
s = 0;
for (int i = 0; i < k; i++) {
nbest[i] = max(best[i], scores[pos][i]);
s += nbest[i];
}
make_options(pos+1, left-1, nbest, ops, s);
}
int bash() {
vector<int> options;
int best[6];
fill(best, best+k, 0);
make_options(0, k, best, options);
sort(options.begin(), options.end(), greater<int>());
return options[c-1];
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> k >> c;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
if (j == 0) {
choose[i][j] = 1;
continue;
}
if (i == 0) {
choose[i][j] = 0;
continue;
}
choose[i][j] = choose[i-1][j]+choose[i-1][j-1];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
cin >> scores[i][j];
sorted[j][i] = pii(scores[i][j], i);
}
}
for (int i = 0; i < k; i++) sort(sorted[i], sorted[i]+n, greater<pii>());
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) sort_pos[sorted[j][i].second][j] = i;
}
pq.push(team());
// int b = bash();
// cerr << b << endl;
while (1) {
team t = pq.top();
pq.pop();
ll hsh = t.get_hsh();
if (vis.find(hsh) != vis.end()) continue;
vis.insert(hsh);
if (t.amt() >= c) {
cout << t.score << "\n";
// assert(t.score == b);
return 0;
}
c -= t.amt();
if (t.amt() > 0) make_dupe(t);
}
}
| # |
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 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
412 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
724 KB |
Output is correct |
| 4 |
Correct |
2 ms |
724 KB |
Output is correct |
| # |
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 |
Correct |
3 ms |
1088 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1088 KB |
Output is correct |
| 5 |
Correct |
1 ms |
596 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
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 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
412 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
2 ms |
724 KB |
Output is correct |
| 8 |
Correct |
2 ms |
724 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1088 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1088 KB |
Output is correct |
| 13 |
Correct |
1 ms |
596 KB |
Output is correct |
| 14 |
Correct |
1 ms |
468 KB |
Output is correct |
| 15 |
Correct |
3 ms |
852 KB |
Output is correct |
| 16 |
Correct |
2 ms |
596 KB |
Output is correct |
| 17 |
Correct |
2 ms |
1020 KB |
Output is correct |
| 18 |
Correct |
3 ms |
848 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
