Submission #677011

#TimeUsernameProblemLanguageResultExecution timeMemory
677011dooompyOlympiads (BOI19_olympiads)C++17
100 / 100
13 ms1992 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...