Submission #643639

#	Time	Username	Problem	Language	Result	Execution time	Memory
643639		Cyanmond	Olympiads (BOI19_olympiads)	C++17	100 / 100	516 ms	1176 KiB

olympiads

#include <bits/stdc++.h>

using i64 = int64_t;
constexpr int inf = 1 << 30;

int main()  {
    int N, K, C;
    std::cin >> N >> K >> C;

    std::vector<std::vector<int>> S(N, std::vector<int>(K));
    for (auto &vec : S) {
        for (auto &e : vec) {
            std::cin >> e;
        }
    }

    std::vector<std::vector<int>> event_scores(K);
    for (auto &vec : S) {
        for (int i = 0; i < K; ++i) {
            event_scores[i].push_back(vec[i]);
        }
    }
    for (auto &vec : event_scores) {
        std::sort(vec.begin(), vec.end(), std::greater());
        vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    }

    struct data {
        int score_sum;
        std::vector<int> ids;
    };

    auto compare = [&](const data &a, const data &b) {
        return a.score_sum < b.score_sum;
    };
    
    auto get_unique_id = [&](const std::vector<int> &ids) {
        i64 res = 0;
        for (int i = 0; i < K; ++i) {
            res += ids[i];
            if (i != K - 1) {
                res *= (i64)event_scores[i + 1].size();
            }
        }
        return res;
    };

    std::priority_queue<data, std::vector<data>, decltype(compare)> heap(compare);
    int init_sum = 0;
    for (int i = 0; i < K; ++i) {
        init_sum += event_scores[i][0];
    }
    heap.push({init_sum, std::vector<int>(K)});
    std::unordered_set<i64> id_set;

    auto get_top = [&]() {
        const auto res = heap.top();
        id_set.insert(get_unique_id(res.ids));
        while ((not heap.empty()) and id_set.find(get_unique_id(heap.top().ids)) != id_set.end()) {
            heap.pop();
        }
        for (int i = 0; i < K; ++i) {
            if (res.ids[i] == (int)event_scores[i].size() - 1) {
                continue;
            }

            int new_sum = res.score_sum - event_scores[i][res.ids[i]];
            new_sum += event_scores[i][res.ids[i] + 1];
            auto new_ids = res.ids;
            ++new_ids[i];
            heap.push({new_sum, new_ids});
        }
        return res;
    };

    auto count_qt = [&](const std::vector<int> &ids) {
        std::vector dp(K + 1, std::vector(1 << K, 0));
        dp[0][0] = 1;

        for (int i = 0; i < N; ++i) {
            bool possible = true;
            int or_b = 0;
            for (int j = 0; j < K; ++j) {
                const auto limit = event_scores[j][ids[j]], score = S[i][j];
                if (limit < score) {
                    possible = false;
                    break;
                } else if (limit == score) {
                    or_b |= 1 << j;
                }
            }
            if (not possible) {
                continue;
            }


            for (int j = K - 1; j >= 0; --j) {
                for (int bit = 0; bit < (1 << K); ++bit) {
                    dp[j][bit] = std::min(dp[j][bit], C);
                    dp[j + 1][bit | or_b] += dp[j][bit];
                }
            }
        }

        return dp[K][(1 << K) - 1];
    };

    int count_top = 0;
    while (count_top < C) {
        const auto [score, ids] = get_top();

        const auto res = count_qt(ids);
        count_top += res;

        if (count_top >= C) {
            std::cout << score << std::endl;
        }
    }
}

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