Submission #1204382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204382		LucaLucaM	Olympiads (BOI19_olympiads)	C++20	100 / 100	7 ms	1668 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;
  std::vector<int> fixed;

  int cost = 0;
  Shard(std::vector<bool> _blocked, std::vector<int> _fixed) : blocked(_blocked), fixed(_fixed) {
    int n = (int) a.size();
    int k = (int) a[0].size();
    chosen.clear();
    cost = 0;
    for (int x : fixed) {
      chosen.push_back(x);
    }
    for (int j = (int) fixed.size(); 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);
    }
  }   

  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), std::vector<int>{}));

  for (int repeat = 1; repeat < c; repeat++) {
    auto u = pq.top();
    pq.pop();
    
    std::vector<bool> block = u.blocked;
    std::vector<int> fixed = u.fixed;

    for (int i = (int) u.fixed.size(); i < k; i++) {
      block[u.chosen[i]] = true;
      auto v = Shard(block, fixed);
      if (v.chosen.back() != -1) {
        pq.push(v);
      } else {
        break;
      }
      fixed.push_back(u.chosen[i]);
    }
  }

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

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