Submission #1204370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204370		LucaLucaM	Olympiads (BOI19_olympiads)	C++20	0 / 100	5 ms	584 KiB

olympiads

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>
#include <queue>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

std::vector<std::vector<int>> a;
std::vector<std::vector<int>> who;

struct Shard {
  std::vector<bool> blocked;
  std::vector<int> chosen;
  int fixed; // [0, fixed) sunt chosen, fixed e blocat
  int cost = 0;
  Shard(std::vector<bool> _blocked, int _fixed) : blocked(_blocked), fixed(_fixed) {
    int n = (int) a.size();
    int k = (int) a[0].size();
    chosen.clear();
    cost = 0;
    for (int j = 0; j < k; j++) {
      for (int i = 0; i < n; i++) {
        if (!blocked[who[j][i]]) {
          bool before = false;
          for (int x : chosen) {
            if (who[j][i] == x) {
              before = true;
              break;
            }
          }
          if (!before) {
            chosen.push_back(who[j][i]);
            break;
          }
        }
      }
    }

    for (int j = 0; j < k; j++) {
      int maxi = 0;
      for (int x : chosen) {
        maxi = std::max(maxi, a[x][j]);
      }
      cost += maxi;
    }

    if ((int) chosen.size() != k) {
      chosen.push_back(-1);
    }
    std::sort(chosen.begin(), chosen.end());
    chosen.erase(std::unique(chosen.begin(), chosen.end()), chosen.end());
  }   

  bool operator < (const Shard &other) const {
    return other.cost > cost;    
  }
};  

int main() {
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n, k, c;
  std::cin >> n >> k >> c;

  a = std::vector<std::vector<int>>(n, std::vector<int>(k));

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

  who = std::vector<std::vector<int>>(k, std::vector<int>(n));

  for (int i = 0; i < k; i++) {
    for (int j = 0; j < n; j++) {
      who[i][j] = j;
    }
    std::sort(who[i].begin(), who[i].end(), [&](int x, int y) {
      return a[x][i] > a[y][i];
    });
  }
  
  std::priority_queue<Shard, std::vector<Shard>> pq;
  pq.push(Shard(std::vector<bool>(n, false), 0));
  int lives = c;
  while (lives > 1) {
    auto u = pq.top();
    pq.pop();
    
    lives--;

    assert((int) u.chosen.size() == k);
    
    while (u.fixed < (int) u.chosen.size()) {
      std::vector<bool> block = u.blocked;
      block[u.chosen[u.fixed]] = true;
      auto v = Shard(block, u.fixed);
      if (v.chosen[0] != -1) {
        pq.push(v);
      }
      u.fixed++;
    }
  }

  std::cout << pq.top().cost;
  
  return 0;
}

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