Submission #396531

#	Time	Username	Problem	Language	Result	Execution time	Memory
396531		KoD	Olympiads (BOI19_olympiads)	C++17	100 / 100	11 ms	10728 KiB

olympiads

#include <bits/stdc++.h>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

class rep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept {
            return itr != other.itr;
        }
        constexpr usize operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr rep(const usize first, const usize last) noexcept
        : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

template <class T> bool setmax(T& lhs, const T& rhs) {
    if (lhs < rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}

template <class T> using Vec = std::vector<T>;

struct State {
    u32 score;
    Vec<u32> member;
    Vec<u32> type;
    bool operator<(const State& other) const { return score < other.score; }
};

void BOI19_Olympiads_main() {
    usize N, K, C;
    std::cin >> N >> K >> C;
    Vec<Vec<u32>> score(K, Vec<u32>(N));
    for (const auto j : rep(0, N)) {
        for (const auto i : rep(0, K)) {
            std::cin >> score[i][j];
        }
    }
    Vec<Vec<usize>> order(K, Vec<usize>(N));
    for (const auto i : rep(0, K)) {
        auto& vec = order[i];
        std::iota(vec.begin(), vec.end(), (usize)0);
        std::sort(vec.begin(), vec.end(), [&](const usize a, const usize b) {
            return score[i][a] > score[i][b];
        });
    }
    std::priority_queue<State> que;
    const auto evaluate = [&](State state) {
        while (state.member.size() < K) {
            const auto i = state.member.size();
            for (const auto x : order[i]) {
                if (state.type[x] == 0) {
                    state.member.push_back(x);
                    state.type[x] = 2;
                    break;
                }
            }
            if (state.member.size() == i) {
                return;
            }
        }
        state.score = 0;
        for (const auto i : rep(0, K)) {
            u32 max = 0;
            for (const auto x : state.member) {
                setmax(max, score[i][x]);
            }
            state.score += max;
        }
        que.push(std::move(state));
    };
    evaluate(State{0, {}, Vec<u32>(N, 0)});
    while (!que.empty()) {
        auto state = que.top();
        que.pop();
        C -= 1;
        if (C == 0) {
            std::cout << state.score << '\n';
            return;
        }
        Vec<usize> change;
        while (!state.member.empty() and state.type[state.member.back()] == 2) {
            change.push_back(state.member.back());
            state.type[state.member.back()] = 0;
            state.member.pop_back();
        }
        usize last = -1;
        while (!change.empty()) {
            const auto exclude = change.back();
            change.pop_back();
            state.type[exclude] = 1;
            if (~last) {
                state.member.push_back(last);
            }
            last = exclude;
            evaluate(state);
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    BOI19_Olympiads_main();
    return 0;
}

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