Submission #403279

#	Time	Username	Problem	Language	Result	Execution time	Memory
403279		rama_pang	Olympiads (BOI19_olympiads)	C++17	100 / 100	8 ms	1336 KiB

olympiads

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, K, C;
  cin >> N >> K >> C;
  vector<vector<int>> A(N, vector<int>(K));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < K; j++) {
      cin >> A[i][j];
    }
  }

  vector<vector<int>> sorted_by(K);
  for (int k = 0; k < K; k++) {
    auto &v = sorted_by[k];
    v.assign(N, 0);
    iota(begin(v), end(v), 0);
    sort(begin(v), end(v), [&](int i, int j) {
      return A[i][k] > A[j][k];
    });
  }

  class Item {
   public:
    int score;
    int forced;
    vector<int> current;
    vector<bool> forbidden;
    const bool operator<(const Item &o) const { return score < o.score; };
  };

  priority_queue<Item> pq;

  const auto Evaluate = [&](const vector<int> &cur) {
    vector<int> res(K, 0);
    for (int i = 0; i < int(cur.size()); i++) {
      int id = sorted_by[i][cur[i]];
      for (int j = 0; j < K; j++) {
        res[j] = max(res[j], A[id][j]);
      }
    }
    return accumulate(begin(res), end(res), 0);
  };

  Item best; // (score, current, forbidden)
  best.forced = 0;
  best.current.assign(K, -1);
  best.forbidden = vector<bool>(N, 0);
  for (int k = 0; k < K; k++) {
    int item = 0;
    while (item < N && best.forbidden[sorted_by[k][item]]) item++;
    assert(item < N);
    best.current[k] = item;
    best.forbidden[sorted_by[k][item]] = 1;
  }
  best.score = Evaluate(best.current);

  pq.emplace(best);
  for (int rep = 0; rep < C - 1; rep++) {
    auto top = pq.top(); pq.pop();
    for (int k = top.forced; k < K; k++) {
      int item = top.current[k];
      top.forbidden[sorted_by[k][top.current[k]]] = true;
      while (item < N && top.forbidden[sorted_by[k][item]]) item++;
      if (item < N) {
        auto nxt = top;
        nxt.forced = k;
        nxt.current[k] = item;
        nxt.score = Evaluate(nxt.current);
        nxt.forbidden[sorted_by[k][item]] = 1;
        pq.emplace(nxt);
      }
    }
  }

  cout << pq.top().score << '\n';
  return 0;
}

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