Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- int64_t get_top_k_sum(const std::vector<std::vector<int>> &X,
- const std::vector<int> &query_idx, int k) {
- size_t n = X.size();
- size_t m = query_idx.size();
- std::vector<int> top_k;
- std::vector<int> all_idx(m, n - 1);
- while (top_k.size() != k) {
- int curr_max = -1;
- int curr_max_i = -1;
- for (size_t i_ = 0; i_ < m; i_++) {
- auto q_i = query_idx[i_];
- auto idx = all_idx[i_];
- if (idx < 0) {
- continue;
- }
- if (X[q_i][idx] > curr_max) {
- curr_max = X[q_i][idx];
- curr_max_i = i_;
- }
- }
- top_k.emplace_back(curr_max);
- all_idx[curr_max_i]--;
- }
- int64_t sum = 0;
- for (auto &elem: top_k) {
- sum += elem;
- }
- return sum;
- }
- int main() {
- int n, k, m, q;
- std::cin >> n >> k >> m >> q;
- std::vector<std::vector<int>> X(n);
- for (size_t i = 0; i < n; i++) {
- std::vector<int> tmp(n, 0);
- for (size_t j = 0; j < n; j++) {
- size_t tmp_num;
- std::cin >> tmp_num;
- tmp[tmp_num - 1]++;
- }
- for (size_t i_ = 0; i_ < tmp.size(); i_++) {
- for (size_t t = 0; t < tmp[i_]; t++) {
- X[i].emplace_back(i_ + 1);
- }
- }
- }
- for (size_t i = 0; i < q; i++) {
- std::vector<int> query_idx(m, 0);
- for (size_t j = 0; j < m; j++) {
- std::cin >> query_idx[j];
- }
- std::cout << get_top_k_sum(X, query_idx, k) << std::endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement