This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
using ll = long long;
int val[505][505];
vector<array<int, 3>> tot;
int n, k, c;
struct state {
int best[7];
bitset<505> banned;
int idx;
vector<int> team;
ll score = 0;
state(bitset<505> _banned, int _idx) : banned(_banned), idx(_idx) {
vector<int>().swap(team);
score = 0;
fill(best, best+7, 0);
int cnt = 0;
for (int i = tot.size() - 1; i >= 0 && cnt < k; i--) {
if (banned[tot[i][1]]) continue;
if (best[tot[i][2]] > 0) continue;
score += tot[i][0];
best[tot[i][2]] = tot[i][0];
cnt++;
bool inteam = false;
for (auto x : team) {
if (x == tot[i][1]) {
inteam =true;
break;
}
}
if (!inteam) {
team.push_back(tot[i][1]);
}
}
if (team.size() < k) {
for (int i = tot.size() - 1; i >= 0 && team.size() < k; i--) {
if (banned[tot[i][1]]) continue;
bool onteam = false;
for (auto x : team) {
if (x == tot[i][1]) {
onteam =true;
break;
}
}
if (onteam) continue;
team.push_back(tot[i][1]);
}
}
}
bool operator<(state o) const {
return score < o.score;
}
};
priority_queue<state> pq;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("", "r", stdin);
// freopen("", "w", stdout);
cin >> n >> k >> c;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
cin >> val[i][j];
tot.push_back({val[i][j], i, j});
}
}
sort(tot.begin(), tot.end());
pq.push({bitset<505>(), 0});
for (int i = 1; i <= c; i++) {
if (pq.empty()) {
cout << -1 << endl;
return 0;
}
auto cur = pq.top(); pq.pop();
if (i == c) {
cout << cur.score << endl;
return 0;
}
while (cur.idx < k) {
// ban current one
bitset<505> nbanned = cur.banned;
nbanned[cur.team[cur.idx]] = true;
auto nw = state(nbanned, cur.idx);
if (nw.team.size() == k) pq.push(nw);
cur.idx++;
}
}
}
Compilation message (stderr)
olympiads.cpp: In constructor 'state::state(std::bitset<505>, int)':
olympiads.cpp:76:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
76 | if (team.size() < k) {
| ~~~~~~~~~~~~^~~
olympiads.cpp:77:65: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
77 | for (int i = tot.size() - 1; i >= 0 && team.size() < k; i--) {
| ~~~~~~~~~~~~^~~
olympiads.cpp: In function 'int main()':
olympiads.cpp:139:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
139 | if (nw.team.size() == k) pq.push(nw);
| ~~~~~~~~~~~~~~~^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |