Submission #1077375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077375		duckindog	Olympiads (BOI19_olympiads)	C++17	100 / 100	31 ms	7212 KiB

olympiads

#include <bits/stdc++.h>

using namespace std;

const int N = 500 + 10;
int n, k, c;
int a[N][10];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> k >> c;
  for (int i = 0; i < n; ++i) { 
    for (int j = 0; j < k; ++j) cin >> a[i][j];
  }

  auto sort = [&](vector<int> &v) {
    for (int i = 0; i < k; ++i) {
      for (int j = i + 1; j < v.size(); ++j)
        if (a[v[j]][i] > a[v[i]][i]) swap(v[i], v[j]);
    }
  };
  auto cal = [&](vector<int> &v) { 
    long long ret = 0;
    for (int i = 0; i < k; ++i) { 
      int ma = 0;
      for (const auto& j : v) ma = max(ma, a[j][i]);
      ret += ma;
    }
    return ret;
  };

  priority_queue<tuple<long long, int, vector<int>>> q;
  { //init
    vector<int> vt(n); iota(vt.begin(), vt.end(), 0);
    sort(vt);
    q.emplace(cal(vt), 0, vt);
  }

  while (q.size()) { 
    auto [value, p, vt] = q.top(); q.pop();
    if (!--c) { cout << value << "\n"; return 0; }
    if (vt.size() == k) continue;
    for (int i = p; i < k; ++i) { 
      vector<int> nxt = vt;
      nxt.erase(nxt.begin() + i);
      sort(nxt);
      q.emplace(cal(nxt), i, nxt);
    }
  }
}

Compilation message (stderr)

olympiads.cpp: In lambda function:
olympiads.cpp:19:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |       for (int j = i + 1; j < v.size(); ++j)
      |                           ~~^~~~~~~~~~
olympiads.cpp: In function 'int32_t main()':
olympiads.cpp:43:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |     if (vt.size() == k) continue;
      |         ~~~~~~~~~~^~~~

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