Advertisement
vlad7576

Untitled

Apr 17th, 2022
1,189
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.64 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. int64_t get_top_k_sum(const std::vector<std::vector<int>> &X,
  5.                       const std::vector<int> &query_idx, int k) {
  6.     size_t n = X.size();
  7.     size_t m = query_idx.size();
  8.     std::vector<int> top_k;
  9.     std::vector<int> all_idx(m, n - 1);
  10.  
  11.     while (top_k.size() != k) {
  12.         int curr_max = -1;
  13.         int curr_max_i = -1;
  14.         for (size_t i_ = 0; i_ < m; i_++) {
  15.             auto q_i = query_idx[i_];
  16.             auto idx = all_idx[i_];
  17.             if (idx < 0) {
  18.                 continue;
  19.             }
  20.             if (X[q_i][idx] > curr_max) {
  21.                 curr_max = X[q_i][idx];
  22.                 curr_max_i = i_;
  23.             }
  24.         }
  25.         top_k.emplace_back(curr_max);
  26.         all_idx[curr_max_i]--;
  27.     }
  28.     int64_t sum = 0;
  29.     for (auto &elem: top_k) {
  30.         sum += elem;
  31.     }
  32.     return sum;
  33. }
  34. int main() {
  35.     int n, k, m, q;
  36.     std::cin >> n >> k >> m >> q;
  37.     std::vector<std::vector<int>> X(n);
  38.     for (size_t i = 0; i < n; i++) {
  39.         std::vector<int> tmp(n, 0);
  40.  
  41.         for (size_t j = 0; j < n; j++) {
  42.             size_t tmp_num;
  43.             std::cin >> tmp_num;
  44.             tmp[tmp_num - 1]++;
  45.         }
  46.         for (size_t i_ = 0; i_ < tmp.size(); i_++) {
  47.             for (size_t t = 0; t < tmp[i_]; t++) {
  48.                 X[i].emplace_back(i_ + 1);
  49.             }
  50.         }
  51.     }
  52.  
  53.     for (size_t i = 0; i < q; i++) {
  54.         std::vector<int> query_idx(m, 0);
  55.         for (size_t j = 0; j < m; j++) {
  56.             std::cin >> query_idx[j];
  57.         }
  58.         std::cout << get_top_k_sum(X, query_idx, k) << std::endl;
  59.     }
  60. }
  61.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement