oj.uz

Submission #131115

# Submission time Handle Problem Language Result Execution time Memory
131115 2019-07-16T14:06:27 Z IOrtroiii Olympiads (BOI19_olympiads) C++14
100 / 100
 181 ms 12036 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1272 KB Output is correct
2 Correct 15 ms 1400 KB Output is correct
3 Correct 14 ms 1276 KB Output is correct
4 Correct 8 ms 760 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 6440 KB Output is correct
2 Correct 97 ms 6288 KB Output is correct
3 Correct 50 ms 2328 KB Output is correct
4 Correct 56 ms 2740 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 12036 KB Output is correct
2 Correct 44 ms 2040 KB Output is correct
3 Correct 140 ms 8428 KB Output is correct
4 Correct 114 ms 8872 KB Output is correct
5 Correct 79 ms 5332 KB Output is correct
6 Correct 48 ms 2104 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1272 KB Output is correct
2 Correct 15 ms 1400 KB Output is correct
3 Correct 14 ms 1276 KB Output is correct
4 Correct 8 ms 760 KB Output is correct
5 Correct 104 ms 6440 KB Output is correct
6 Correct 97 ms 6288 KB Output is correct
7 Correct 50 ms 2328 KB Output is correct
8 Correct 56 ms 2740 KB Output is correct
9 Correct 131 ms 12036 KB Output is correct
10 Correct 44 ms 2040 KB Output is correct
11 Correct 140 ms 8428 KB Output is correct
12 Correct 114 ms 8872 KB Output is correct
13 Correct 79 ms 5332 KB Output is correct
14 Correct 48 ms 2104 KB Output is correct
15 Correct 181 ms 12016 KB Output is correct
16 Correct 159 ms 11940 KB Output is correct
17 Correct 45 ms 2296 KB Output is correct
18 Correct 74 ms 4280 KB Output is correct
19 Correct 42 ms 2044 KB Output is correct