oj.uz

답안 #643639

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
643639 2022-09-22T17:11:34 Z Cyanmond Olympiads (BOI19_olympiads) C++17
100 / 100
 516 ms 1176 KB 
#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.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 384 KB Output is correct
2 Correct 17 ms 596 KB Output is correct
3 Correct 23 ms 672 KB Output is correct
4 Correct 22 ms 724 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 12 ms 364 KB Output is correct
4 Correct 10 ms 360 KB Output is correct
5 Correct 14 ms 372 KB Output is correct
6 Correct 2 ms 340 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 10 ms 384 KB Output is correct
6 Correct 17 ms 596 KB Output is correct
7 Correct 23 ms 672 KB Output is correct
8 Correct 22 ms 724 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 12 ms 364 KB Output is correct
12 Correct 10 ms 360 KB Output is correct
13 Correct 14 ms 372 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 516 ms 828 KB Output is correct
16 Correct 136 ms 540 KB Output is correct
17 Correct 348 ms 1176 KB Output is correct
18 Correct 487 ms 860 KB Output is correct
19 Correct 2 ms 340 KB Output is correct