Submission #396473

#	Time	Username	Problem	Language	Result	Execution time	Memory
396473		KoD	Olympiads (BOI19_olympiads)	C++17	0 / 100	10 ms	2360 KiB

olympiads

#include <bits/stdc++.h>

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

template <class F>
struct RecLambda: private F {
    explicit RecLambda(F&& f): F(std::forward<F>(f)) { }
    template <class... Args>
    decltype(auto) operator () (Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

struct State {
    int sum;
    Vec<int> idx;
    Vec<bool> use;
    bool operator < (const State& other) const {
        return sum < other.sum;
    }
};

int main() {
    int N, K;
    long long C;
    std::cin >> N >> K >> C;
    Vec<Vec<int>> get(N, Vec<int>(K));
    for (auto& v: get) {
        for (auto& x: v) {
            std::cin >> x;
        }
    }
    Vec<Vec<int>> order(K, Vec<int>(N));
    for (int i = 0; i < K; ++i) {
        auto& vec = order[i];
        std::iota(vec.begin(), vec.end(), 0);
        std::stable_sort(vec.begin(), vec.end(), [&](const int x, const int y) {
            return get[x][i] > get[y][i];
        });
    }
    Vec<Vec<long long>> binom(N + 1, Vec<long long>(K + 1));
    binom[0][0] = 1;
    for (int i = 1; i <= N; ++i) {
        binom[i][0] = 1;
        for (int j = 1; j <= K; ++j) {
            binom[i][j] = binom[i - 1][j] + binom[i - 1][j - 1];
        }
    }
    const auto calc = [&](State& state) {
        state.sum = 0;
        for (int i = 0; i < K; ++i) {
            state.sum += get[order[i][state.idx[i]]][i];
            state.use[order[i][state.idx[i]]] = false;
        }
    };
    State initial {
        0,
        Vec<int>(K, 0),
        Vec<bool>(N, true),
    };
    calc(initial);
    std::priority_queue<State> que;
    que.push(std::move(initial));
    while (!que.empty()) {
        const auto state = que.top();
        que.pop();
        std::set<int> set;
        for (int i = 0; i < K; ++i) {
            set.insert(order[i][state.idx[i]]);
        }
        C -= binom[std::count(state.use.begin(), state.use.end(), true)][K - (int) set.size()];
        if (C <= 0) {
            std::cout << state.sum << '\n';
            return 0;
        }
        for (int i = 0; i < K; ++i) {
            State next = state;
            auto& idx = next.idx[i];
            while (idx < N and !next.use[order[i][idx]]) {
                idx += 1;
            }
            if (idx < N) {
                calc(next);
                que.push(std::move(next));
            }
        }
    }
    return 0;
}

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