oj.uz

Submission #403279

# Submission time Handle Problem Language Result Execution time Memory
403279 2021-05-13T01:56:36 Z rama_pang Olympiads (BOI19_olympiads) C++17
100 / 100
 8 ms 1336 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 316 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 5 ms 716 KB Output is correct
3 Correct 5 ms 716 KB Output is correct
4 Correct 4 ms 568 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 6 ms 900 KB Output is correct
4 Correct 6 ms 844 KB Output is correct
5 Correct 7 ms 1336 KB Output is correct
6 Correct 5 ms 716 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 316 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 5 ms 716 KB Output is correct
7 Correct 5 ms 716 KB Output is correct
8 Correct 4 ms 568 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 6 ms 900 KB Output is correct
12 Correct 6 ms 844 KB Output is correct
13 Correct 7 ms 1336 KB Output is correct
14 Correct 5 ms 716 KB Output is correct
15 Correct 4 ms 460 KB Output is correct
16 Correct 7 ms 1080 KB Output is correct
17 Correct 8 ms 1324 KB Output is correct
18 Correct 5 ms 716 KB Output is correct
19 Correct 3 ms 332 KB Output is correct