Submission #131115

#	Time	Username	Problem	Language	Result	Execution time	Memory
131115		IOrtroiii	Olympiads (BOI19_olympiads)	C++14	100 / 100	181 ms	12036 KiB

olympiads

#include <bits/stdc++.h>

using namespace std;

int n, k, c;
int a[505][6];
vector<int> go[505];
set<vector<int>> was;

int getVal(vector<int> cur) {
   int ans = 0;
   for (int i = 0; i < k; ++i) {
      int mx = 0;
      for (int v : cur) {
         mx = max(mx, a[v][i]);
      }
      ans += mx;
   }
   return ans;
}

struct cmp {
   bool operator()(const vector<int> &l, const vector<int> &r) {
      return getVal(l) < getVal(r);
   }
};

int main() {
   ios_base::sync_with_stdio(false);
   cin >> n >> k >> c;
   for (int i = 0; i < n; ++i) {
      for (int j = 0; j < k; ++j) {
         cin >> a[i][j];
      }
   }
   vector<int> opt;
   for (int j = 0; j < k; ++j) {
      vector<pair<int, int>> vals;
      for (int i = 0; i < n; ++i) {
         vals.emplace_back(a[i][j], i);
      }
      sort(vals.begin(), vals.end());
      reverse(vals.begin(), vals.end());
      opt.push_back(vals[0].second);
      for (int i = 0; i < n; ++i) {
         go[i].push_back(vals[0].second);
      }
      for (int i = 0; i + 1 < n; ++i) {
         go[vals[i].second].push_back(vals[i + 1].second);
      }
   }
   sort(opt.begin(), opt.end());
   opt.resize(unique(opt.begin(), opt.end()) - opt.begin());
   for (int i = 0; i < n; ++i) {
      if (opt.size() < k && find(opt.begin(), opt.end(), i) == opt.end()) {
         opt.push_back(i);
      }
   }
   sort(opt.begin(), opt.end());
   priority_queue<vector<int>, vector<vector<int>>, cmp> q;
   q.push(opt);
   was.insert(opt);
   for (int it = 0; it < c - 1; ++it) {
      vector<int> cur = q.top();
      q.pop();
      for (int i = 0; i < k; ++i) {
         int v = cur[i];
         for (int u : go[v]) {
            vector<int> nxt = cur;
            nxt[i] = u;
            sort(nxt.begin(), nxt.end());
            nxt.resize(unique(nxt.begin(), nxt.end()) - nxt.begin());
            if (nxt.size() < k) {
               continue;
            }
            if (!was.count(nxt)) {
               q.push(nxt);
               was.insert(nxt);
            }
         }
      }
   }
   cout << getVal(q.top()) << "\n";
}

Compilation message (stderr)

olympiads.cpp: In function 'int main()':
olympiads.cpp:55:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (opt.size() < k && find(opt.begin(), opt.end(), i) == opt.end()) {
           ~~~~~~~~~~~^~~
olympiads.cpp:73:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (nxt.size() < k) {
                 ~~~~~~~~~~~^~~

• Subtask 1: 13 / 13
• Subtask 2: 31 / 31
• Subtask 3: 24 / 24
• Subtask 4: 32 / 32