#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 512;
const int maxk = 8;
int n, k, c;
int p[maxn][maxk];
struct State {
int score, start;
int best[maxk]; // indices of people in team
bitset<maxk> forbidden; // indices already used
State() {
start = 0;
forbidden.reset();
calc_score();
}
State(State* pre, int new_start) {
start = new_start;
forbidden = pre->forbidden;
forbidden[pre->best[start]] = true;
for (int i = 0; i < start; ++i) {
best[i] = pre->best[i];
}
calc_score();
}
void calc_score() {
for (int j = start; j < k; ++j) {
int besti = -1;
int bests = -1e9;
for (int i = 0; i < n; ++i) {
if (forbidden[i] || in_best(j, i)) {
continue;
}
if (p[i][j] > bests) {
bests = p[i][j];
besti = i;
}
}
if (besti == -1) {
score = -1e6;
return;
}
best[j] = besti;
}
score = 0;
for (int j = 0; j < k; ++j) {
int res = 0;
for (int i = 0; i < k; ++i) {
res = max(res, p[best[i]][j]);
}
score += res;
}
}
bool in_best(int end, int x) {
for (int i = 0; i < end; ++i) {
if (best[i] == x) {
return true;
}
}
return false;
}
};
struct State_Compare {
bool operator () (State* l, State* r) {
return l->score < r->score;
}
};
priority_queue<State*, vector<State*>, State_Compare> pq;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> k >> c;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < k; ++j) {
cin >> p[i][j];
}
}
int ans = 0;
pq.push(new State());
State* top;
while (c) {
top = pq.top();
pq.pop();
ans = top->score;
for (int i = top->start; i < k; ++i) {
pq.push(new State(top, i));
}
--c;
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
632 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
6 ms |
632 KB |
Output is correct |
| 4 |
Correct |
4 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
504 KB |
Output is correct |
| 2 |
Correct |
6 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
504 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
